# 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.

Output:

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.

Output:

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++

Output:

(2 votes, average: 5.00 out of 5)

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 🙂

Subscribe
Notify of
Guest
Bogdan Dumitru

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 🙂