• Nodes: up to 100,000
• Must be O(N) time and O(1) space.

We want to determine if the values in a singly linked list form a palindrome, reading the exact same forward and backward. However, a linked list is a one-way chain of memory addresses; we can only traverse forward. We cannot index elements directly from the back, nor can we iterate backward from the tail. How can we check for symmetry across both ends of the list when we can only travel in one direction?

The most straightforward approach is to copy every node's value into a standard array. Once we have a flat array, we can use two converging pointers starting at the front and back to verify the symmetry.

While this runs in linear time, it requires O(N) extra memory to hold all the copied values. If our list contains millions of elements, allocating this extra array can easily exhaust our memory buffer.

# Copy all values to an array
vals = []
curr = head
while curr:
    vals.append(curr.val)
    curr = curr.next

# Verify symmetry using two pointers
left, right = 0, len(vals) - 1
while left < right:
    if vals[left] != vals[right]:
        return False
    left += 1
    right -= 1
return True

To check for a palindrome with absolutely zero extra memory, we execute a three-step surgery in-place using these pointer states:
- Midpoint Finders (slow, fast): Pointers traveling at 1x and 2x speeds respectively to find the list's exact center.
- Reversal Pointers (prev, curr, nxt): Standard pointer states to flip the links of the second half backward.
- Parallel Scanners (p1, p2): Two pointers traversing the first and reversed second halves in unison.

Our strategy is to find the exact midpoint, reverse the second half of the list in-place so its links point backward from the tail, and then run a parallel scan. By flipping the second half's arrows, we can start one scanner at the head and another at the tail (which is now the head of the reversed second half) and step both inward toward the center. This gives us O(1) space symmetry validation.

First, we find the middle using our slow and fast pointers. Next, we reverse the list starting from the slow pointer. Finally, we walk both halves in parallel, comparing their values. If any mismatch occurs, we return false.

# Phase 1: Find the middle node
slow = head
fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# Phase 2: Reverse the second half in-place
prev = None
curr = slow
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt

# Phase 3: Compare both halves
p1 = head
p2 = prev  # Head of the reversed second half
is_palindrome = True

while p2:  # The reversed half is equal or shorter
    if p1.val != p2.val:
        is_palindrome = False
        break
    p1 = p1.next
    p2 = p2.next

return is_palindrome

The mirrored surgery handles boundary structures perfectly:
- Odd Lengths (e.g. [1, 2, 1]): The slow pointer lands exactly on the middle node (2). The second half [2, 1] is reversed to [1, 2]. When comparing, p2 traverses [1, 2], while p1 traverses [1, 2]. They match successfully.
- Single Node List: fast.next is null initially. slow stays at index 0. The reversed second half is just [1], which matches the first half perfectly in 1 step.