Apr 24, 2012

Check if the linked list is a palindrome

The following code checks if the given singly linked list is a palindrome using recursion. 
Time Complexity: O(n) 
Space Complexity: O(n)
C++ Program
bool isPalindrome() const
    {
      Node* node = isPalindrome(head, head);
      if(node)
        return true;
      return false;
    }

    Node* isPalindrome(Node *left, Node *right) const
    {
      if(right == NULL)
      {
        return left;
      }

      left = isPalindrome(left, right->link);
      if(left)
      {
        bool palindrome = left->ch == right->ch ? true : false;
        if(palindrome)
        {
          left = left->link ? left->link : left;
          return left;
        }
      }
      return NULL;
    }
Java Program
public boolean isPalindrome()
  {
    Node node = isPalindrome(head, head);
    if(node == null)
      return false;
    return true;
  }

  private Node isPalindrome(Node left, Node right)
  {
    if(right == null)
    {
      return left;
    }
  
    left = isPalindrome(left, right.link);
    if(left != null)
    {
      boolean palindrome = left.data == right.data ? true : false;
      if(palindrome)
      {
        left = (left.link != null) ? left.link : left;
        return left;
      }
    }
    return null;
  }

1 comment :

Anonymous said...

an explanation would have been nice

Post a Comment