Palindrome Linked List LeetCode 234

LeetCode 234 Palindrome Linked List gives you the head of a singly linked list and asks you to determine whether the list is a palindrome — that is, whether the sequence of node values reads the same forward and backward. Return true if it is a palindrome, false otherwise.

The straightforward follow-up that interviewers always ask: can you solve it in O(n) time and O(1) extra space? Copying values to an array is easy but uses O(n) space. The O(1) space solution requires mutating the list itself, which means understanding three core linked list primitives and composing them carefully.

Knowing the constraints helps size your approach. The list length can reach 100,000 nodes, so any O(n²) approach like comparing each node against its mirror by traversal will time out. The key insight is that you do not need random access — you only need to walk both halves simultaneously once the list is set up correctly.

The simplest O(n) space approach copies all node values into an array or list, then uses a two-pointer technique on the array: one pointer starting from index 0 and one from the last index, walking inward and comparing values. If any pair mismatches, return false. If all pairs match, return true. This is clean, easy to reason about, and perfectly correct — but uses O(n) extra space for the array.

A second O(n) space approach uses the call stack recursively. You can write a recursive function that walks to the end of the list, then compares values on the way back out. The recursion depth equals the list length, so in the worst case the call stack holds O(n) frames. While elegant, this approach risks a stack overflow for lists of 100,000 nodes in languages without tail-call optimization.

Both approaches are worth mentioning in an interview to show breadth, but the O(1) space solution is what the problem is really testing. The O(1) approach is also the most instructive — it reveals the underlying structure of three fundamental linked list operations working together.

Use two pointers: slow starts at head and moves one node at a time, fast starts at head and moves two nodes at a time. When fast reaches the end of the list (fast is None or fast.next is None), slow is pointing at the middle node. This is the classic tortoise-and-hare middle-finding technique.

For an odd-length list of length 2k+1, slow will stop at the exact center node — index k (0-indexed). For an even-length list of length 2k, slow will stop at the second of the two middle nodes — index k. In both cases, the second half of the list begins at slow.next, which is where we start the reversal.

The stopping condition matters. When fast reaches the last node (fast.next is None), slow is at the middle. When fast steps off the end (fast is None), slow has advanced one extra step. The correct stopping condition is to stop before fast steps off the end so that slow lands at the last node of the first half (for even length) or the exact middle (for odd length).

Starting from slow.next (the head of the second half), reverse the second half of the linked list using the standard iterative reversal technique. Use three pointers: prev initialized to None, curr initialized to slow.next, and next_node as a temporary pointer. In each iteration, save curr.next to next_node, point curr.next back to prev, advance prev to curr, and advance curr to next_node. When curr becomes None, prev is the new head of the reversed second half.

After reversal, you have two independent sub-lists: the first half starting at head (ending at slow, which still points to the last node of the first half) and the reversed second half starting at prev (the new tail of the reversed half points to None). Both halves can now be traversed from their respective heads for comparison.

It is important to disconnect the first half from the second half by setting slow.next = None before (or after) the reversal. This prevents the comparison loop from accidentally following stale pointers. Some implementations set slow.next = None as a cleanup step; others rely on the None terminator of the reversed second half to stop the comparison loop naturally.

Walk both halves simultaneously: pointer left starts at head, pointer right starts at prev (the head of the reversed second half). At each step compare left.val and right.val. If they ever differ, the list is not a palindrome — record false. Advance both pointers by one. The loop ends when right becomes None (the reversed second half is exhausted).

If all compared values matched, the list is a palindrome. Return true. If any mismatch was found, return false. The comparison is inherently O(n/2) — roughly half the list length — but simplifies to O(n) in asymptotic notation.

If the problem or interview requires the list to be left unmodified after the check, reverse the second half again before returning. Reversing it a second time restores the original order. This is a non-destructive variant: reverse second half, compare, reverse back, return result. The extra reversal is O(n/2) and does not change the overall O(n) time complexity.

Python solution: define isPalindrome(head) with three helpers or inline logic. Find middle: slow = fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next. Reverse second half: prev = None; curr = slow.next; while curr: nxt = curr.next; curr.next = prev; prev = curr; curr = nxt. Compare: left, right = head, prev; result = True; while right: if left.val != right.val: result = False; left = left.next; right = right.next. Return result. O(n) time, O(1) space.

Java solution: public boolean isPalindrome(ListNode head). Find middle: ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }. Reverse: ListNode prev = null, curr = slow.next; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; }. Compare: ListNode left = head, right = prev; while (right != null) { if (left.val != right.val) return false; left = left.next; right = right.next; } return true. O(n) time, O(1) space.

Both solutions use identical logic structured as three sequential phases. The Java solution short-circuits on the first mismatch by returning false immediately inside the comparison loop, which can save work for long non-palindromes. The Python version collects a boolean result and returns it after the loop — functionally equivalent but slightly less efficient for early failures. Both are accepted as optimal O(n)/O(1) solutions on LeetCode.

Reorder List (LeetCode 143) uses the exact same two-step setup: find the middle with fast/slow pointers, reverse the second half in place. Instead of comparing the two halves, you interleave them. The palindrome check is essentially a read-only version of Reorder List — if you understand one you understand the other. Both problems share the same O(1) space setup phase.

Reverse Linked List II (LeetCode 92) isolates the reversal step used in this problem. It asks you to reverse a sublist from position left to position right in one pass. Mastering iterative in-place reversal here directly applies to palindrome checking and reorder list. Linked List Cycle II (LeetCode 142) uses fast/slow pointers in a different context — finding the cycle entry point — but the same two-speed pointer technique is the foundation.

The broader linked list composition family includes problems that combine find-middle, reverse, and merge as building blocks. Middle of the Linked List (LeetCode 876) isolates the first step. Reverse Linked List (LeetCode 206) isolates the second step. Palindrome Linked List (LeetCode 234) and Reorder List (LeetCode 143) combine all three. Studying these as a family rather than individually accelerates pattern recognition for any linked list problem.