Jun 122012
 

Write a function to check if a Singly linked list is a palindrome or not. For example, the linked list

2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 is a palindrome
M -> A -> L -> A-> Y -> A -> L -> A -> M is a palindrome
2 -> 3 -> 4 -> 5 -> 4 -> 6 -> 2 is NOT a palindrome
K -> A -> M -> A -> L is NOT a palindrome

The function should take O(n) time in worst case.

Solution:

Method-1: Use Recursion

You need to compare the first and last node in the first loop and then compress the list

Time Complexity: O(n2)

    bool isPalindrome(Node* head)
    {
       return isPalindromeRec(&head, head);
    }

    bool isPalindromeRec(Node **l, Node *r)
    {
       if (!r)      // terminating condition
          return true;

       // If the sublist is not palindrome then don't need to check further
       if (! isPalindromeRec(l, r->link) )
          return false;     

       bool flag = (r->data == (*l)->data);
       *l = (*l)->link; // Move l forward

       return flag;
    }

Method-2: Use reverse method

Step 1. Move to the middle of the list.
Step 2. Reverse the second half
Step 3. compare the first and reversed second half one node at a time, 
         if they are same return true 
         else return false.
Step 4. Reverse the 2nd half again to get the original list.

Time Complexity: O(n)
Extra Space used: O(1)

  One Response to “Check if a linked list is palindrome”

Comments (1)
  1. The method 2 is more efficient but not easy to implement.
    Find our discussion and source code in Java for both approaches here http://www.capacode.com/data-structure/linked-list/check-linked-list-palindrome/

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)