Mirror of a Binary Tree
June 12, 2012
Crossing the Bridge in 17 min, Puzzle
June 12, 2012

Check if a linked list is palindrome

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)

1 Comment

  1. Khanh says:

    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 to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *