Community Problem
Palindrome Linked List
Difficulty: Easy
Decide whether a singly-linked list reads the same forward and backward in O(n) time and O(1) space using fast/slow pointers plus an in-place reverse of the second half.
Palindrome Linked List
Decide whether a singly-linked list reads the same forward and backward in O(n) time and O(1) space using fast/slow pointers plus an in-place reverse of the second half.
By CodeSnatch
February 21, 2026
·
Updated May 20, 2026
974 views
12
4.6 (16)
Picked this as the EASY-tier official Cat 5 entry because it's the cleanest place to teach the fast/slow + reverse-half pattern, which shows up again in Reorder List, Sort List, and Reverse Nodes in K-Group. The naive solution copies the values into an array and runs a two-pointer compare in O(n) extra space; the senior signal is the in-place version.
Palindrome Linked List
Given the head of a singly-linked list, return true if the list reads the same forward and backward, false otherwise. Each node stores an integer in its val field and a reference to the next node in next.
Examples
Example 1:
- Input:
head = [1, 2, 2, 1] - Output:
true - Explanation: Reading forwards and backwards both give
1, 2, 2, 1.
Example 2:
- Input:
head = [1, 2] - Output:
false - Explanation: Reverse is
2, 1.
Example 3:
- Input:
head = [1] - Output:
true - Explanation: A single-node list is trivially a palindrome.
Example 4:
- Input:
head = [1, 2, 3, 2, 1] - Output:
true - Explanation: Odd-length palindrome with a middle node.
Constraints
- The number of nodes in the list is in the range
[1, 10^5]. 0 <= Node.val <= 9
Follow-up
Can you do it in O(n) time and O(1) extra space? The interview answer is: walk fast/slow to find the midpoint, reverse the second half in place, then compare halves with two pointers from the outside in.
Solution
Hints
Approach
The naive O(n) extra space solution copies values to an array and runs a two-pointer comparison. The interview-grade version is O(n) time and O(1) extra space, achieved by reversing the second half in place.
Key insight
Reversing the second half lets us walk both halves in the same direction at the same time without random access. Fast/slow pointers find the midpoint in one pass; the reverse is the standard prev/cur/next dance; the final comparison is plain two-pointer walking.
Algorithm
- Edge cases: if
headis null or has only one node, returntrue. - Fast/slow walk:
slow = head,fast = head, advance whilefastandfast.nextare non-null. After the loop,slowis the start of the second half (for even length,slowis the (n/2)th node; for odd length,slowis the exact middle). - Reverse from
slow: standardprev = null,cur = slow, withcur.nextflipped toprev. After the loop,previs the head of the reversed second half. - Walk
left = headandright = prevtogether whilerightis non-null. If any pair of values differs, returnfalse. Otherwise returntrue.
Complexity
Metric Value
------ -----
Time O(n)
Space O(1) auxiliaryThree linear passes, each O(n), no extra structures.
Why it works
For an odd-length list n = 2m + 1, fast/slow stops with slow at index m (the exact middle). Reversing from m flips the back half; the comparison walks left = head and right = reversed-from-m, which compares index i vs n - 1 - i. The middle element compares against itself and is skipped because right ends one step early.
For an even-length list n = 2m, fast/slow stops with slow at index m (start of the second half). Same comparison logic, no middle to skip.
Pitfalls
- Walking
leftandrightwhile BOTH are non-null instead of justright. The reversed second half is shorter or equal, so usewhile (right !== null)to avoid steppingleftoff the end of an even-length first half. - Forgetting to handle the single-node and null cases. Return
trueimmediately. - Using a recursive reverse instead of iterative on long lists: that's
O(n)stack space and breaks theO(1)claim. - Sandpack
for...ofquirks do not apply here because we never iterate Map/Set; the linked-list traversal is plainwhileloops on.next.
Solution Code