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

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(n²)

    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)