Palindrome Linked List
Last Updated: March 29, 2026
Understanding the Problem
A palindrome reads the same forwards and backwards. With an array, you would just compare elements from both ends moving inward. But a singly linked list only lets you traverse in one direction, so you can't easily walk backwards from the tail.
That's the core challenge here: how do you compare elements from the front and back of a structure that only supports forward traversal? There are a few ways to work around this limitation, each with different trade-offs between simplicity, time, and space.
Key Constraints:
The number of nodes is in the range [1, 10^5]→ With up to 100,000 nodes, O(n^2) approaches would be borderline. O(n) is clearly preferred.0 <= Node.val <= 9→ Values are single digits. This is a small detail but means we don't need to worry about overflow or large value comparisons.- The list has at least one node, so we don't need a null-check for an empty list.
Approach 1: Copy to Array
Intuition
The simplest way to handle the "can't traverse backwards" problem: just copy all the values into an array, then use the classic two-pointer palindrome check. Arrays support random access, so comparing from both ends is straightforward.
This converts a linked list problem into an array problem, which is a useful technique when the list's constraints (no random access, no backward traversal) are getting in the way.
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 approach works correctly but uses extra space. Is there a way to compare the first half and second half of the list without copying everything into an array?
Approach 2: Reverse Second Half (Optimal)
Intuition
Here's the key insight: if we find the middle of the linked list, we can reverse the second half in-place, then compare both halves node by node. No extra array needed.
Finding the middle is a classic technique: use a slow pointer (moves 1 step at a time) and a fast pointer (moves 2 steps at a time). When fast reaches the end, slow is at the middle. Then we reverse the list from slow onward and walk both halves simultaneously, comparing values.
The slow/fast pointer technique guarantees that slow lands at the middle (or just past it for odd-length lists). After reversing from that point, the reversed half has exactly as many nodes as the first half (or one fewer for odd lists). Comparing node by node from both ends tells us if the list is a palindrome.
For odd-length lists like [1, 2, 3, 2, 1], slow ends up at the middle node (3). Reversing from there gives us 1 → 2 → 3. We compare 1,2 from the first half against 1,2 from the reversed half. The middle element (3) doesn't need comparison since it pairs with itself.
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.