Determine if a given linked list is a palindrome or not

Given a singly linked list of integers, determine if the linked list is a palindrome or not.


 

For example,


Input:  1 -> 2 -> 3 -> 2 -> 1 -> null
Output: The linked list is a palindrome

 
Input:  1 -> 2 -> 3 -> 3 -> 1 -> null
Output: The linked list is not a palindrome

 
The idea is to traverse the linked list and push all encountered elements into the stack. Then we traverse the linked list again and for each node, we pop the top element from the stack and compare it with the node’s data. If a mismatch happens for any node, we can say that the linked list is not a palindrome.

 

Download   Run Code

Output:

Linked List is a palindrome.

 
Time complexity of above solution is O(n). The auxiliary space required by the solution is O(n) for the stack container.

We can find out if a linked list is a palindrome in linear time and with constant space. The idea is to split the given list into two halves and reverse the second half. Then we traverse both lists simultaneously and compare their data. If a mismatch happens for any node, we can say that the linked list is not a palindrome.

Since the solution modifies the given list, we need to restore the original linked list. This can be done by simply linking the first half with the second half.

 

Download   Run Code

Output:

Linked List is a palindrome.

 
We can avoid modification of the original list (even temporarily) with the power of recursion. Below is simple C++ recursive implementation that works by recursing till end of the list and checking each node of the linked list for palindrome as the recursion unfolds.

C++

Download   Run Code

Output:

Linked list is Palindrome

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

Loading...

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Bogdan Dumitru
Guest

Hi TechieDelight,

First off, many thanks for maintaining this site! I’ve used it while interviewing, and it’s a really great resource.

For this problem, I believe we could also design a rather elegant solution, which does not use extra memory (apart from the call stack involved in recursion), and does not modify (even temporarily) the original list.

Like this (pseudo-code):

And yes, this performs every check twice, but that’s fine. Or we could keep a running total while “recursing forward” and only to 1/2 * total checks while “recursing back”, but I thought it’s not worth the effort 🙂

Thanks again for your efforts,
– Bogdan