Reverse Linked List

Given the head of a singly linked list, reverse the list in place and return the new head. The machine must walk the chain once, flipping each node's next pointer to point backward, without allocating a second list.

The key insight: a singly linked list node only knows its successor, so when you redirect a next pointer you lose access to the rest of the list. You must capture the next node before rewriting the pointer — that is what the third pointer is for.

Approach:

1. Initialize prev = None and curr = head.
2. For each node: save next_node = curr.next, then set curr.next = prev, then advance prev = curr and curr = next_node.
3. When curr reaches None, prev is the new head.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Time: O(n), one pass. Space: O(1), no extra structure.

Trickiest edge case: the empty list — the loop never runs and prev stays None, which is correctly the return value. A recursive variant is elegant but costs O(n) stack space; the iterative version is what you want in production.