On this page
Description
Checking whether a singly linked list is a palindrome looks like it needs walking backwards, which the list can't do. Instead, combine two moves you already know. Find the middle with fast and slow pointers, reverse the second half in place, and compare the two halves from the outside in. Swap the comparison for an interleaving merge, and the same moves solve Reorder List.
We'll go from simple to more technical:
- The pattern: middle, reverse the second half, compare.
- A second flavor: interleave the halves instead (Reorder List).
- Why composing small building blocks is a habit worth having.
- The details that differ between the two uses: odd middles, the cut, and restoring the list.
The approach
A palindrome reads the same both ways. So the second half, read backwards, must match the first half read forwards. You can't read a singly linked list backwards, but you can reverse its second half in place and then read it forwards.
Checking 3 -> 8 -> 5 -> 8 -> 3:
| Step | What happens |
|---|---|
| 1. Find the middle | fast and slow pointers: slow stops on 5 |
| 2. Reverse from the middle | the back half 5 -> 8 -> 3 becomes 3 -> 8 -> 5 |
| 3. Compare from both fronts | 3 = 3, 8 = 8, 5 = 5: the reversed half is used up, so it's a palindrome |
For 3 -> 8 -> 5 -> 2 -> 3, the reversed back half is 3 -> 2 -> 5, and the second comparison, 8 against 2, fails. With an odd length, the middle node ends up compared with itself, so it needs no special case.
1. Find the middle with fast/slow pointers (see two-pointer-list-traversal).
2. Reverse the second half in place (see singly-linked-list-basics).
3. Walk the original first half and the reversed second half together,
comparing values - any mismatch means it's not a palindrome.
Nothing new is invented here. "Find the middle" says where to split, and "reverse in place" turns the back half into something you can read forwards.
A second flavor: interleaving instead of comparing
Keep the same first two moves, but change the third. Instead of comparing the halves, weave them together. That reorders L0, L1, ..., Ln into L0, Ln, L1, Ln-1, L2, .... For example, 3 -> 8 -> 5 -> 2 -> 6 becomes 3 -> 6 -> 8 -> 2 -> 5.
Java
ListNode secondHead = slow.next;
slow.next = null; // cut the first half away from the second
ListNode second = reverse(secondHead); // same reversal building block as before
ListNode first = head;
while (second != null) {
ListNode t1 = first.next, t2 = second.next;
first.next = second;
second.next = t1;
first = t1;
second = t2;
}
Python
second_head = slow.next
slow.next = None # cut the first half away from the second
second = reverse(second_head) # same reversal building block as before
first = head
while second is not None:
t1, t2 = first.next, second.next
first.next = second
second.next = t1
first, second = t1, t2
One new detail: cut the first half off from the second (slow.next = null) before reversing and weaving. Comparing never changes any next, so a leftover link did no harm there. Weaving rewires next pointers, and a leftover link turns into a cycle.
Where you'll see it
The lesson here is the habit more than the problem. Most medium interview problems, and a lot of production code, combine a few small, well-understood pieces. When a task looks new, ask which building blocks it's made of before inventing anything.
Which tool for which job?
| You need | Use |
|---|---|
| Palindrome check, O(1) space | middle + reverse second half + compare |
| The same, simplest code | copy the values into an array and compare ends |
| The caller's list unchanged | reverse the second half back afterwards |
| A check over a stream you read once | forward and backward rolling hashes |
| Reorder L0, Ln, L1, Ln-1, ... | middle + cut + reverse + interleave |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Worrying about the odd middle | extra code for nothing | it matches itself - compare until the reversed half ends |
| Leaving the list half-reversed | the caller sees a shorter, broken list | reverse the second half back |
| No cut before interleaving | a cycle appears | set the first half's last next to null |
| Reading the list while another thread checks it | the reader sees the half-reversed list | copy, or don't mutate shared lists |
| Comparing past the reversed half | null dereference | loop while the second pointer isn't null |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. With an odd number of nodes, why doesn't the middle node need a match?
Show answer
Reversing from the middle puts the middle node at the end of both halves you compare. When the walk reaches it, it's compared with itself, which always matches. So no special case is needed.
2. The check must leave the caller's list unchanged. What extra step does the reversal method need?
Show answer
Reverse the second half back before returning. The in-place reversal really changed the list's links, not just how you read them. Copying the values into an array never touches the list, which is the trade-off: simpler, but O(n) extra space.
3. Why does weaving the halves need a cut first, when comparing them doesn't?
Show answer
Comparing only reads values and never changes a next, so an uncut link is never followed. Weaving reassigns next pointers. An uncut link from the first half into the second then becomes part of a cycle.
Key takeaways
- A palindrome check combines two known moves: find the middle, reverse in place. Then compare.
- The same moves with a different last step reorder the list instead.
- An odd middle node is compared with itself, so it needs no special case.
- The reversal changes the list. Reverse it back if the caller needs it intact.
- Cut the halves apart before any step that rewires them.