Palindrome Linked List
Understanding the Problem
A palindrome reads the same forwards and backwards. With an array, you compare elements from both ends moving inward. A singly linked list only allows traversal in one direction, so there is no way to walk backwards from the tail.
The core challenge is comparing elements from the front and back of a structure that only supports forward traversal. Two approaches handle this: copy the values into an array that does support random access, or find the middle and reverse the second half in place to compare it against the first.
Key Constraints:
- The number of nodes is in the range
[1, 10^5]. With up to 100,000 nodes, any O(n^2) comparison would be too slow, so the target is O(n) time. 0 <= Node.val <= 9. Values are single digits, so there is no overflow concern when comparing them.- The list has at least one node, so an empty-list check is unnecessary.
Approach 1: Copy to Array
Intuition
Copy all the node values into an array, then run the standard two-pointer palindrome check. An array supports random access, so comparing from both ends is direct.
This converts the linked list problem into an array problem, which sidesteps the lack of backward traversal at the cost of extra memory.
Algorithm
- Traverse the linked list and copy each node's value into an array.
- Use two pointers,
leftstarting at index 0 andrightstarting at the last index. - Compare values at
leftandright. If they differ, returnfalse. - Move
leftforward andrightbackward. Repeat until they meet or cross. - If all comparisons matched, return
true.
Example Walkthrough
Code
- Time Complexity: O(n). One pass to copy all n values into the array, and one pass with two pointers to check for palindrome. Both are O(n).
- Space Complexity: O(n). We store all n values in an auxiliary array.
This uses O(n) extra space for the array. The next approach removes that array by rearranging the list itself.
Approach 2: Reverse Second Half (Optimal)
Intuition
If we find the middle of the linked list, we can reverse the second half in place and then compare both halves node by node, using no extra array.
To find the middle, advance a slow pointer one step and a fast pointer two steps at a time. When fast reaches the end, slow sits at the start of the second half. Reversing the list from slow onward lets us walk the first half forward and the reversed second half forward at the same time, comparing values as we go.
When fast moves twice as fast as slow, slow reaches the start of the second half after fast has covered the whole list. For an even length the two halves have equal size; for an odd length the second half (starting at slow) has one extra node, the middle. The comparison loop runs while right != null, so it stops once the reversed second half is exhausted. For an odd list like [1, 2, 3, 2, 1], slow stops at the middle node (val 3), and the reversed second half becomes 1 → 2 → 3. The loop compares the first half 1, 2, 3 against 1, 2, 3, so the middle node is compared against itself and never breaks the palindrome. Because right (the shorter or equal half) controls the loop, left is never advanced past the list end.
Algorithm
- Use slow/fast pointers to find the middle of the list. When fast reaches the end, slow points to the start of the second half.
- Reverse the second half of the list starting from slow.
- Compare nodes from the head of the original list and the head of the reversed second half.
- If any values differ, return
false. If all match, returntrue. - (Optional) Reverse the second half again to restore the original list.
Example Walkthrough
Code
- Time Complexity: O(n). Finding the middle takes O(n/2). Reversing the second half takes O(n/2). Comparing both halves takes O(n/2). All three are O(n) total.
- Space Complexity: O(1). We only use a constant number of pointer variables. No extra data structures. This answers the follow-up question.