Palindrome Linked List
Problem
Given the head of a singly linked list, return true if it is a palindrome or false otherwise.
- The number of nodes in the list is in the range [1, 10⁵]
- 0 ≤ Node.val ≤ 9
Example
head = [1, 2, 2, 1]trueThe algorithm uses two pointers: 'fast' moves two steps at a time, 'slow' moves one step. When 'fast' reaches the end, 'slow' is at the midpoint. For the input [1, 2, 2, 1], 'slow' stops at the second '2'. The second half starting from 'slow' is reversed, resulting in [1, 2]. Then, the algorithm compares nodes from the start and from the reversed second half. Since all corresponding nodes match, it returns true.
Approach
Straightforward Solution
A brute-force approach copies the linked list values into an array and checks if the array is a palindrome. This requires O(n) extra space and two passes.
Core Observation
A palindrome reads the same forwards and backwards. For a singly linked list, this means the first half of the list must match the reversed second half.
Path to Optimal
The key insight is to find the midpoint using fast and slow pointers, reverse the second half in-place, and then compare the two halves node-by-node. This approach uses O(1) extra space and only a few passes over the list.
Optimal Approach
Use two pointers to find the midpoint. Reverse the second half of the list in-place. Then iterate from the head and from the reversed half simultaneously, comparing values. If all match, return true; otherwise, false. This approach is O(n) time and O(1) space.
Time
O(n)
The list is traversed a constant number of times: once to find the midpoint, once to reverse the second half, and once to compare halves, each O(n).
Space
O(1)
Reversing the second half in-place and using pointers for comparison requires only constant extra space, excluding input storage.
Pattern Spotlight
Fast & Slow Pointers (Midpoint Detection and In-Place Reversal)
Use a fast pointer moving twice as fast as a slow pointer to find the midpoint in a single pass, then reverse the second half in-place to enable direct comparison without extra space.
Solution
| 1 | class Solution: |
| 2 | def isPalindrome(self, head): |
| 3 | slow = fast = head |
| 4 | |
| 5 | while fast and fast.next: |
| 6 | slow = slow.next |
| 7 | fast = fast.next.next |
| 8 | |
| 9 | prev = None |
| 10 | while slow: |
| 11 | nxt = slow.next |
| 12 | slow.next = prev |
| 13 | prev = slow |
| 14 | slow = nxt |
| 15 | |
| 16 | left = head |
| 17 | right = prev |
| 18 | |
| 19 | while right: |
| 20 | if left.val != right.val: |
| 21 | return False |
| 22 | left = left.next |
| 23 | right = right.next |
| 24 | |
| 25 | return True |
Step-by-Step Solution
Locate the Middle of the Linked List Using Fast and Slow Pointers
| 3 | slow = fast = head |
| 5 | while fast and fast.next: |
| 6 | slow = slow.next |
| 7 | fast = fast.next.next |
Objective
To find the midpoint of the linked list efficiently in a single pass.
Key Insight
Using two pointers moving at different speeds allows detection of the midpoint without knowing the list length upfront. The fast pointer moves two nodes per iteration, the slow pointer moves one. When the fast pointer reaches the end, the slow pointer is at the midpoint, splitting the list into two halves for further processing.
Interview Quick-Check
Core Logic
Fast pointer moves twice as fast as slow pointer, so when fast reaches the end, slow is at midpoint.
State & Boundaries
Loop condition checks both fast and fast.next to avoid null pointer exceptions.
Common Pitfalls & Bugs
Failing to check fast.next can cause runtime errors when fast reaches the last node.
Reverse the Second Half of the List In-Place
| 9 | prev = None |
| 10 | while slow: |
| 11 | nxt = slow.next |
| 12 | slow.next = prev |
| 13 | prev = slow |
| 14 | slow = nxt |
Objective
To reverse the nodes from the midpoint to the end, enabling backward traversal for comparison.
Key Insight
Reversing the second half in-place transforms the singly linked list into two halves that can be traversed forward simultaneously. This avoids extra space usage and allows direct value comparison. The reversal uses a standard iterative approach with three pointers: previous, current, and next.
Interview Quick-Check
Core Logic
Iteratively reverse the second half by redirecting next pointers, using a prev pointer to build the reversed list.
State & Boundaries
Loop continues until slow pointer reaches the end, ensuring full reversal of the second half.
Common Pitfalls & Bugs
Not saving slow.next before reassigning can lose access to the remaining list.
Compare the First Half and Reversed Second Half Node-by-Node
| 16 | left = head |
| 17 | right = prev |
| 19 | while right: |
| 20 | if left.val != right.val: |
| 21 | return False |
| 22 | left = left.next |
| 23 | right = right.next |
Objective
To verify if the linked list is a palindrome by comparing corresponding nodes from both halves.
Key Insight
After reversal, the first half and the reversed second half can be traversed in parallel. If any pair of nodes differ in value, the list is not a palindrome. If all pairs match, the list is a palindrome. This comparison is linear and stops as soon as a mismatch is found.
Interview Quick-Check
Core Logic
Traverse both halves simultaneously, comparing node values to confirm palindrome property.
State & Boundaries
Loop until the right pointer (reversed half) is exhausted, as it may be shorter for odd-length lists.
Common Pitfalls & Bugs
Failing to return false immediately upon mismatch leads to incorrect results.
Return True if All Node Comparisons Match
| 25 | return True |
Objective
To conclude the palindrome check by returning true after successful comparison.
Key Insight
If the entire reversed second half matches the first half, the linked list is a palindrome. Returning true here signals successful verification after all checks.
Interview Quick-Check
Core Logic
Return true only after confirming all corresponding nodes match.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
slow.next = prevReverse the current node's next pointer to point to prev.
Redirecting slow.next to prev reverses the link, building the reversed list incrementally.
nxt = slow.nextSave the next node before changing pointers.
Storing slow.next preserves access to the remainder of the list after pointer reversal.
if left.val != right.val:Check if current node values differ.
A mismatch indicates the list is not a palindrome, allowing early termination.
return FalseReturn false immediately upon value mismatch.
Early return prevents unnecessary comparisons once a difference is found, optimizing performance.
while fast and fast.next:Begin loop to advance slow and fast pointers.
The loop condition ensures traversal continues only while fast and fast.next exist, preventing null pointer errors.
slow = slow.nextMove slow pointer one step forward.
Slow pointer advances at half the speed of fast, so it will reach the midpoint when fast reaches the end.
fast = fast.next.nextMove fast pointer two steps forward.
Fast pointer moves twice as fast, enabling detection of the midpoint by the time it reaches the list's end.
return TrueReturn true after successful comparison of all nodes.
If no mismatches were found, the list is a palindrome, so returning true confirms this.
slow = fast = headInitialize slow and fast pointers at the head of the list.
Starting both pointers at the head sets up the fast-slow pointer technique to find the midpoint efficiently.
while slow:Loop through the second half starting at slow pointer.
This loop iterates over the second half to reverse the links in-place.
prev = slowMove prev pointer to current slow node.
Prev advances to the newly reversed node, maintaining the head of the reversed list.
slow = nxtAdvance slow pointer to the saved next node.
Moving slow forward continues the reversal process through the second half.
while right:Loop while right pointer is not null.
Looping over the reversed half ensures all nodes are compared; the reversed half may be shorter for odd-length lists.
prev = NoneInitialize prev pointer to None for reversal.
Prev pointer tracks the head of the reversed list segment, starting empty before reversal begins.
left = headInitialize left pointer at the head of the list.
Left pointer traverses the first half for comparison with the reversed second half.
right = prevInitialize right pointer at the head of the reversed second half.
Right pointer traverses the reversed second half to compare node values.
left = left.nextAdvance left pointer to next node.
Moving left forward continues the comparison along the first half.
right = right.nextAdvance right pointer to next node.
Moving right forward continues the comparison along the reversed second half.
Test Your Understanding
Why does reversing the second half of the list enable palindrome checking in O(1) space?
Because reversing the second half allows direct node-by-node comparison with the first half without extra data structures, eliminating the need to store values separately.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Palindrome Linked List from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Palindrome Linked List drill