Reorder List

Given the head of a singly linked list, reorder it in place so that the nodes alternate first, last, second, second-to-last, and so on. The machine cannot allocate a new list — it must physically rewire the existing nodes.

The key insight: the reordering is a zip of the first half with the reversed second half. Three subproblems compose: find the midpoint, reverse the second half, then interleave. Midpoint discovery uses the slow-fast pointer trick; the second half is reversed with the standard three-pointer flip.

Approach:

1. Walk slow/fast to split the list at the midpoint; cut the halves apart.
2. Reverse the second half iteratively.
3. Merge: take one node from the first half, then one from the reversed second half, advancing both until the second half is exhausted.

def reorder_list(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev, curr = curr, nxt
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next, second.next = second, tmp1
        first, second = tmp1, tmp2

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

Trickiest edge case: odd-length lists — the split must leave the middle node in the first half, and the merge loop runs only while the (shorter) reversed half still has nodes, or the machine dereferences None.