Fast & Slow — Palindrome Linked List
↗ LeetCode: Palindrome Linked List · Easy · pattern chapter →
Given the head of a singly linked list, return true iff it's a palindrome.
Example 1 — 1 → 2 → 2 → 1 → trueExample 2 — 1 → 2 → falseExample 3 — 1 → true
Constraints — 1 ≤ n ≤ 10⁵. Follow-up: O(n) time, O(1) space. Brute copy to array + two-pointer is O(n) time + O(n) space. Fast/slow to midpoint + reverse-second-half + compare is O(n) time + O(1) space — ~10⁶ pointer ops.
Interview timer00:00
Approach 1 — Copy to array, two-pointer
Intuition. Materialize into int[], then classic two-pointer palindrome check.
boolean isPalindromeArr(ListNode head) {
List<Integer> a = new ArrayList<>();
for (ListNode c = head; c != null; c = c.next) a.add(c.val);
int l = 0, r = a.size() - 1;
while (l < r) if (!a.get(l++).equals(a.get(r--))) return false;
return true;
}Complexity — Time O(n); Space O(n).
Approach 2 — Reverse second half in place (O(1) space)
Insight from array. We can compare in place by splitting the list at the middle (fast/slow), reversing the second half, then walking two pointers from head and reversed-head.
Trap — restore the list at the end for good citizenship in library code (interviewers care). The naive version leaves the list mutated.
boolean isPalindrome(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
// slow is at second-half start (or exact middle for odd length)
ListNode second = reverse(slow);
ListNode secondHead = second;
ListNode p1 = head, p2 = second;
boolean ok = true;
while (p2 != null) {
if (p1.val != p2.val) { ok = false; break; }
p1 = p1.next; p2 = p2.next;
}
// restore
reverse(secondHead);
return ok;
}
ListNode reverse(ListNode h) {
ListNode prev = null;
while (h != null) { ListNode n = h.next; h.next = prev; prev = h; h = n; }
return prev;
}Complexity — Time O(n) (3 passes); Space O(1).
Approach 3 — Recursive comparison (O(n) stack)
Insight. Recurse to end; compare with a "front pointer" as recursion unwinds.
ListNode front;
boolean isPalindromeRec(ListNode head) {
front = head;
return check(head);
}
boolean check(ListNode node) {
if (node == null) return true;
if (!check(node.next)) return false;
if (node.val != front.val) return false;
front = front.next;
return true;
}Complexity — Time O(n); Space O(n) call stack. Cleaner code but same asymptotics as Approach 1.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Copy to array | O(n) | O(n) | baseline |
| Reverse second half in place | O(n) | O(1) | canonical follow-up |
| Recursive front pointer | O(n) | O(n) stack | elegant but same space |
When to use which
- Standard interview → reverse-half in-place.
- Interviewer allows O(n) extra → copy-to-array is safer and clearer.
- "Restore list at end" → always mention; some interviewers require it.
- Doubly linked list → true two-pointer O(1) space and no reversal.
Related problems
- Middle of the Linked List — the split primitive
- Reverse Linked List — the reversal primitive
- Reorder List — same split + reverse + interleave