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

## C

Output:

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

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 🙂