Palindrome Linked List

Palindrome Linked List asks a simple question — does the list read the same forwards and backwards? — but doing it in O(1) extra space forces a neat trick: find the middle, reverse the back half in place, then walk inward from both ends.

The slow way first

The obvious idea: copy every value into an array, then check whether the array equals its reverse. That works and is easy to write, but it uses O(n) extra space for the array.

The question to ask: can I compare the front and back without copying anything? In an array I could use two pointers from both ends — but a singly linked list has no way to walk backwards. So the move is to make the back half walkable in reverse, in place.

The idea: split, reverse, compare

Do it in three phases, all with constant extra space:

1. Find the middle with a slow/fast pointer. fast moves two steps for every one of slow, so when fast falls off the end, slow sits at the middle.
2. Reverse the second half in place by flipping each next pointer backwards (the classic three-pointer reverse).
3. Walk both halves inward: one pointer from the original head, one from the new head of the reversed back half. Compare values as they meet in the middle.

The key insight: once the back half points backwards, the two halves can be scanned toward each other in a single pass, with no array and no recursion stack.

Walk through it

Step through the animation with 1 -> 2 -> 2 -> 1. In phase 1, slow advances one node and fast two, so fast lands on the last node and slow marks the middle. In phase 2, the link 2 -> 1 is flipped to 1 -> 2, so the back half now starts at the last node. In phase 3, left starts at the head and right at that reversed head; we compare 1 == 1, then 2 == 2, the pointers meet, and the verdict is Palindrome.

Pseudocode

slow = fast = head
while fast and fast.next:        # find the middle
    slow = slow.next
    fast = fast.next.next
prev = None                      # reverse the second half
curr = slow.next
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
left = head                      # compare the two halves
right = prev
while right:
    if left.val != right.val:
        return False
    left = left.next
    right = right.next
return True

The Python solution

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    curr = slow.next
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    left = head
    right = prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

• Lines 2-5 are the slow/fast walk. Because fast covers two nodes per step, it reaches the end in half the time, leaving slow at the middle.
• Lines 6-12 are the in-place reverse of the second half — the same save / flip / advance loop used to reverse any linked list. prev ends up at the new head of the reversed back half.
• We compare against right (the reversed half) until it runs out. Walking right until None naturally stops at the middle, so for an odd-length list the leftover middle node is simply ignored.
• The first mismatch returns False early; if the loop finishes, every pair matched and we return True.

Complexity

Both approaches are O(n) time, but this one uses only O(1) extra space — no array, no recursion stack. The cost is a little more pointer bookkeeping, which is exactly what interviewers want to see.

When this pattern shows up

Practice