Check if a 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 recursion stack and a pointer to the beginning of the linked list.


Download   Run Code


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.


Download   Run Code


Linked list is Palindrome

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

can i get the solutions in c?