Palindrome Linked List

Given the head of a singly linked list, determine whether the sequence of values reads the same forward and backward. The machine must decide in O(1) space — no copying the values into an array, which would be the easy O(n)-space answer.

The key insight: a palindrome is a list whose second half, reversed, equals its first half. So the machine splits the list at its midpoint, reverses the second half in place, and compares the two halves element by element. Midpoint finding uses the slow-fast pointer walk; reversing is the standard three-pointer flip.

Approach:

1. Walk slow/fast to the midpoint; slow lands on the start of the second half.
2. Reverse the second half iteratively.
3. Compare nodes from head and the reversed half; restore the list if required.

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

Time: O(n), three linear passes. Space: O(1).

Trickiest edge case: odd-length lists — the midpoint lands on the center node, which is its own mirror, so it can be included in the reversed half without breaking the comparison.