Check if a Linked List is Palindrome
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
A palindrome is a sequence that reads the same backward and forward. For example:
1 → 2 → 3 → 2 → 1 is a palindrome. 1 → 2 → 3 → 4 is not a palindrome.
This problem is simple in words but tricky in execution because, unlike arrays, linked lists do not allow direct backward traversal.
In this article, we’ll go step by step, starting from a brute force approach and finally reaching the optimal O(n) time and O(1) space solution.
7 → 2 → 8 → 2 → 7
Output : true1 → 2 → 3 → 1
Output : false- The number of nodes in the list is in the range [1, 105].
- 0 <= Node.val <= 9
- Do it in O(n) time and O(1) space
Approach 1: Brute force Approach
Brute force Approach is to copy all linked list elements into an array (or list) and then check if the array is a palindrome.
- Traverse the linked list and store all values in an array.
- Use two pointers (left and right) to check if the array is a palindrome.
- Return the result.
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isPalindrome(ListNode* head) {
vector<int> list;
while (head != NULL) {
list.push_back(head->val);
head = head->next;
}
int left = 0, right = list.size() - 1;
while (left < right) {
if (list[left] != list[right])
return false;
left++;
right--;
}
return true;
}
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(1);
cout << "Is linked list palindrome? "
<< (isPalindrome(head) ? "true" : "false") << endl;
}Is linked list palindrome? true
Time Complexity : O(N)
Space Complexity : O(N)
Easy to implement. ❌ Not optimal because of extra space usage.
Approach 2: Recursive Check
Another elegant way to solve the palindrome linked list problem is by using recursion.
The key idea is that recursion naturally goes to the end of the list first (deep into the call stack) and then comes back one node at a time (unwinding). This behavior allows us to compare nodes from both ends of the linked list without explicitly reversing it or using extra arrays.
- Start recursion from the head of the list.
- Keep moving to the end of the list (right pointer goes deep).
- On the way back (while recursion unwinds):
- Compare the current right node with a global left pointer (which starts at the head).
- If values match, move the left pointer one step forward.
- If a mismatch is found, return false immediately.
- In this way: The recursion depth mimics moving from start to end and The left pointer moves forward as recursion comes back, simulating end-to-start traversal.
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeLinkedList {
public:
ListNode* left; // global pointer
bool isPalindrome(ListNode* head) {
left = head;
return checkRecursively(head);
}
private:
bool checkRecursively(ListNode* right) {
if (right == NULL) return true;
bool isPal = checkRecursively(right->next);
if (!isPal) return false;
if (left->val != right->val) return false;
left = left->next;
return true;
}
};
int main() {
ListNode* head1 = new ListNode(1);
head1->next = new ListNode(2);
head1->next->next = new ListNode(2);
head1->next->next->next = new ListNode(1);
PalindromeLinkedList pll;
cout << "Is linked list 1->2->2->1 palindrome? "
<< (pll.isPalindrome(head1) ? "true" : "false") << endl;
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
head2->next->next = new ListNode(3);
cout << "Is linked list 1->2->3 palindrome? "
<< (pll.isPalindrome(head2) ? "true" : "false") << endl;
}Is linked list 1->2->2->1 palindrome? true Is linked list 1->2->3 palindrome? false
Time Complexity : O(N)
Space Complexity : O(N) , recursion adds stack frames, making it less memory-efficient.
The recursive approach is a beautiful demonstration of recursion’s power in linked list problems. However, it’s mainly useful for learning and interviews. It is very clean and elegant solution. Easy to understand once you’re familiar with recursion but not optimal for large lists because of O(n) extra space usage.
Approach 3: Optimal Solution (O(n) Time, O(1) Space)
When working with linked lists, the brute force method (copying values into an array and checking both ends) is simple but not memory-efficient. The real challenge comes when you’re asked to check if a singly linked list is a palindrome using O(1) extra space. This means we must work directly with the linked list without storing its values elsewhere.
- Find the middle of the linked list ( Using Slow & Fast Pointers)
- Use two pointers: slow moves 1 step, fast moves 2 steps.
- When fast reaches the end, slow will be at the middle.
- Reverse the second half of the list.
- Reverse the linked list starting from slow.next.
- Example: 2 → 1 becomes 1 → 2
- This allows us to compare the first half and the reversed second half directly.
- Compare the first half and the reversed second half.
- Compare node values of first half and reversed second half one by one.
- If all match → palindrome. Otherwise → not a palindrome.
- Restore the list to its original form.
- If the problem expects the original list to remain unchanged, we reverse the second half again to restore it. This step is optional but good practice in production systems.
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* secondHalf = reverse(slow);
ListNode* firstHalf = head;
ListNode* temp = secondHalf;
while (temp) {
if (firstHalf->val != temp->val) return false;
firstHalf = firstHalf->next;
temp = temp->next;
}
return true;
}
private:
ListNode* reverse(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr) {
ListNode* nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
};
int main() {
Solution sol;
ListNode* head1 = new ListNode(1);
head1->next = new ListNode(2);
head1->next->next = new ListNode(2);
head1->next->next->next = new ListNode(1);
cout << "Is linked list 1->2->2->1 palindrome? "
<< (sol.isPalindrome(head1) ? "true" : "false") << endl;
ListNode* head2 = new ListNode(1);
head2->next = new ListNode(2);
head2->next->next = new ListNode(3);
cout << "Is linked list 1->2->3 palindrome? "
<< (sol.isPalindrome(head2) ? "true" : "false") << endl;
}Is linked list 1->2->2->1 palindrome? true Is linked list 1->2->3 palindrome? false
Time Complexity : O(N)
Space Complexity : O(1)
Comparison of Approaches
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Convert to Array | O(n) | O(n) | Simple, but extra space |
| Recursive Check | O(n) | O(n) (stack) | Clean, but uses recursion stack |
| Optimal (Reverse Half) | O(n) | O(1) | Best choice for interviews |