Problem Understanding
Starting from head, decide whether the values of a singly linked list read the same from front to back as from back to front.
Example: 1 -> 2 -> 2 -> 1 is true. 1 -> 2 is false.
Attempt 1: Copy to Array (Brute Force)
The simplest way is to copy all node values into an array (or ArrayList) and then check if the array is a palindrome using two pointers. This is easy to implement but requires O(N) extra space.
Visualizing the Issue
Can we do this in O(1) space? We can't traverse backwards in a singly linked list. However, if we could reverse the second half of the list, we could compare it with the first half!
The Intuition: Middle & Reverse
- Find the Middle of the list (using Tortoise and Hare).
- Reverse the second half of the list in-place.
- Compare the start of the list with the start of the reversed half.
- This solution stops there and does not restore the list: when it returns, the second half is still reversed. Reverse it again before returning if the caller needs the list intact.
Interactive Walkthrough
[1, 2, 2, 1]
START AT HEAD
head slow fast
#0
→
#1
→
#2
→
#3
→ NULL
Phase
middle
Answer
—
slow and fast start at head, node 0 (1)
Next
slow moves one node to node 1 (2); fast moves two to node 2 (2)
Values
Watch slow and fast find the middle, then each link in the second half flip to point back toward the middle — the reversed half becomes its own row, ending where it joins the first half. left and right then compare values pair by pair. The last step shows the list as the code leaves it: second half still reversed.