Check If Linked List Is Palindrome

The idea is to store the list values in a stack and then compare the values in the list with the values in the stack.
 

Algorithm:

1. Traverse the list from head to tail and push every node in the stack.
2. Make a pointer ‘cur’ which initially points to the head node.
3. If value at ‘cur’ is not equal to the top element of the stack, then the given list is not a palindrome
4. Else, move the ‘cur’ pointer to its next node and pop the top element from the stack.
5. If stack is empty,  then the given list is a palindrome
6. Else, repeat the steps 3 to 6.

Approach:

The idea is to reach the end of the list and then compare if the last node has the same value as the first node, the second last node has the same value as the second node and so on..

For comparing node values we will use a the recursion stack.

For example, if the given list is (1 -> 2 -> 3 -> 2 -> 1).

First we will traverse the list upto last node. Now, when we are coming out of the Nth recursive state, list (1 -> 2 -> 3 -> 2 -> 1) will be present in the recursive stack with the right node being 1 (Nth node), when we are coming out of the (N-1)th recursive state, list (1 -> 2 -> 3 -> 2 -> 1) will be present in the recursive stack with the right node being 2 ((N-1)th node), and so on…

So, when we are coming out of Nth recursive state, we will compare Nth node with 1st node,when we are coming out of (N-1)th recursive state, we will compare (N-1)th node with 2nd node,... when we are coming out of 2nd recursive state, we will compare 2nd node with (N-1)th node, when we are coming out of 1st recursive state, we will compare 1st node with Nth node.

If all these states return true, then the list is a palindrome.
 

Algorithm:

Make a recursive function isPalindromeHelper(left, right) {pass left pointer by its reference}, this function checks whether the list between left and right is palindrome or not.

• Call the function: isPalindromeHelper(head, head).
• Base case: if right is equal to NULL, return true
• Call the next recursive state: isPalindromeHelper(left, right->next).
• If the sub-list is not palindrome or the value at ‘left’ node is not equal to ‘right’ node, return false.
• Else, move the ‘left’ pointer to its next node and return true from the current recursive state.

The idea is to divide the list into two halves from mid and reverse the second half. If both halves are equal then the given list is palindrome.

• Divide the list into two lists ‘first’ and ‘second’.
  • Make two pointers ‘slow’ and ‘fast’ which initially points to the head node.
  • Move ‘slow’ and ‘fast’ pointer as follows until ‘fast’ becomes NULL:
    • slow = slow->next
    • fast = fast->next->next
  • ‘First’ list will contain nodes from head to previous node of ‘slow’.
  • ‘Second’ list will contain nodes from slow to ‘tail’ of the given list.
  • Reverse the ‘second’ list.
• Now, traverse the two lists and compare node values (if the number of nodes in the given list is odd, then the ‘second’ list will contain one node more than the ‘first’ list, for this we can neglect the last node of the ‘second’ list).