Palindrome Linked List Solution

Problem

Given a singly linked list, determine whether its values read the same forwards and backwards. You cannot simply index into it — you must traverse it with pointers.

→

→∅

[1,2,2,1]

Input: head = [1, 2, 2, 1]
Output: true
Explanation: The sequence 1 → 2 → 2 → 1 is identical whether read left-to-right or right-to-left.

Counter-example:

→

→∅

[1,2,3,1]

Input: head = [1, 2, 3, 1]
Output: false
Explanation: 1 → 2 → 3 → 1 reversed is 1 → 3 → 2 → 1, which differs at the inner elements.

Intuition

The simplest way to check a palindrome is to collect all values and use two pointers converging from both ends. The insight behind the O(1)-space approach is that you do not need to store anything — you can reverse the second half of the list in-place and then walk both halves together, comparing node by node.

Approach 1 — Copy to Array

Collect every value into a list, then use left/right pointers to verify symmetry. Simple to reason about but costs O(n) extra memory.

Walk the list from head to tail, appending each value to an array.
Set left = 0 and right = len - 1.
While left < right, compare values[left] and values[right]; return false on any mismatch.
Advance left forward and right backward after each comparison.
Return true if no mismatch was found.

1def isPalindrome(self, head: Optional[ListNode]) -> bool:
2    values = []
3    current = head
4    while current:
5        values.append(current.val)
6        current = current.next
7
8    left, right = 0, len(values) - 1
9    while left < right:
10        if values[left] != values[right]:
11            return False
12        left += 1
13        right -= 1
14    return True

Time: O(n) — single pass to collect, single pass to compare.
Space: O(n) — stores all n values in the array.

Approach 2 — Reverse Second Half In-Place

Find the midpoint with slow/fast pointers, reverse the second half in-place, then compare the two halves node by node. No extra memory needed beyond a few pointers.

Use slow and fast pointers — slow advances one step, fast two — stopping when fast.next or fast.next.next is None. Slow then sits at the last node of the first half.
Reverse the sublist beginning at slow.next, producing a reversed second half whose head is the original tail.
Walk first from head and second from the reversed second-half head simultaneously, comparing values.
Return false on the first mismatch, true if second is exhausted without one.

1def isPalindrome(self, head: Optional[ListNode]) -> bool:
2    slow, fast = head, head
3    # Stop when slow is at the last node of the first half
4    while fast.next and fast.next.next:
5        slow = slow.next
6        fast = fast.next.next
7
8    # Reverse from slow.next onward
9    prev, current = None, slow.next
10    while current:
11        next_node = current.next
12        current.next = prev
13        prev = current
14        current = next_node
15    second_half_head = prev  # now points to the original tail
16
17    # Compare first half (head…slow) with reversed second half
18    first, second = head, second_half_head
19    while second:
20        if first.val != second.val:
21            return False
22        first = first.next
23        second = second.next
24    return True

Time: O(n) — three linear passes (find mid, reverse, compare).
Space: O(1) — only a constant number of pointer variables.

Complexity Summary

Approach	Time	Space	When to use
Copy to Array	O(n)	O(n)	When clarity matters more than memory, or the list must not be mutated
Reverse Second Half	O(n)	O(1)	Whenever you need constant extra memory and can tolerate temporarily modifying the list

Common Mistakes

Using while fast and fast.next instead of while fast.next and fast.next.next — the wrong condition lets slow advance one step too far on even-length lists, so the second half contains only the last element and misses inner comparisons. [1,2,3,1] would incorrectly return true because only 1 == 1 is checked.
Starting the reversal from slow rather than slow.next — when the list has odd length, slow sits on the true middle node; reversing from slow pulls the middle into the second half and causes an off-by-one mismatch during comparison.
Comparing second.next != null as the loop condition — this skips the last node of the second half entirely; the correct guard is while second so every reversed node is checked.
Forgetting that the second half is shorter or equal, never longer — when iterating, always drive the loop with second (the shorter or equal-length half), not first, otherwise first.next may be null before second is exhausted and you'll get a null-pointer crash.
Leaving the list permanently reversed — in systems where the structure must be preserved after the check, you need to reverse the second half back again (slow.next = reverse(secondHalfHead)); omitting this silently corrupts the list for any caller that reads it afterward.

Palindrome Linked List — Solution