Check if linked list is palindrome or not

Given a linked list, check if linked list is palindrome or not.

 


 

Simple solution would be to create clone of the linked list, reverse it and check if both linked lists are equal or not. This approach requires three traversals of the linked list and requires extra space for storing duplicates list.

 

Better solution would be to use recursion. The idea is to reach to the end of the linked list by recursion and then compare if last node has same value as first node and second last node has same value as second node and so on.. using recusion stack and a pointer to the beginning of the linked list.

 
C++ implementation –
 

Download   Run Code

Output:

Linked list is Palindrome

 


 

The time complexity of above solution is O(n) and need O(n) extra space for the call stack.
 

We can solve this problem in constant space and linear time by dividing the problem into three subproblems –

  • Divide the list into two equal parts.
     
  • Reverse the second half.
     
  • Check if first and second half are similar. If the linked list contains odd number of nodes then, then ignore middle element.
     

C++ implementation –
 

Download   Run Code

Output:

Linked list is Palindrome

 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂