Palindrome Linked List
Easy · Two Pointers · Explanation and code example
Fast & Slow Pointers
How it works
To achieve O(1) extra space, we can reverse the second half of the list in place. Then we compare the first half with the reversed second half node by node.
We use the fast and slow pointer technique to find the middle of the list. The fast pointer moves twice as fast, so when it reaches the end, the slow pointer is at the middle.
Steps
- Use fast and slow pointers to find the middle of the list. When fast reaches the end, slow is at the middle.
- Reverse the second half of the list starting from slow.
- Compare nodes from the head and from the reversed second half. If any values differ, return
false. - Continue until the reversed half is fully traversed.
- Return
trueif all comparisons match.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)extra space.
Things to watch for
Incorrect Middle Finding for Odd-Length Lists
When using fast and slow pointers, for odd-length lists the slow pointer ends up at the exact middle element. If you reverse starting from slow, the middle element ends up in the reversed half. This still works because we only compare until the reversed half is exhausted, but misunderstanding this can lead to off-by-one errors in the comparison loop.
Not Restoring the Original List
The in-place reversal approach modifies the original linked list structure. If the problem requires the list to remain unchanged after the function call, or if subsequent operations depend on the original structure, you must reverse the second half back to its original order after the palindrome check.
Python code example
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
fast = head
slow = head
# find middle (slow)
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# reverse second half
prev = None
while slow:
tmp = slow.next
slow.next = prev
prev = slow
slow = tmp
# check palindrome
left, right = head, prev
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
C++ code example
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *fast = head, *slow = head;
// find middle (slow)
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
// reverse second half
ListNode *prev = nullptr;
while (slow) {
ListNode *tmp = slow->next;
slow->next = prev;
prev = slow;
slow = tmp;
}
// check palindrome
ListNode *left = head, *right = prev;
while (right) {
if (left->val != right->val) {
return false;
}
left = left->next;
right = right->next;
}
return true;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.