p06 Reverse Linked List — Progressive Hints

Rule: Read ONE hint. Set a 5-minute timer. Try again. Only read the next hint if the timer expires.

Hint 1 — Pattern family

You’re going to rewrite next pointers in place. Before you overwrite a pointer, ask: “do I still need it?” If yes, save it somewhere first.

Hint 2 — Data structure / state

You need to track THREE things at every step: where you came from (so the current node can point there), where you are (the node being rewired), and where you were about to go (so you don’t lose the rest of the list).

Hint 3 — The key insight

Walk left to right. At each node, the previously-seen node becomes its new next. But before you set curr.next = prev, you must remember the old curr.next because that’s the only way to advance.

Hint 4 — Pseudocode skeleton

prev = None
curr = head
while curr is not None:
    next_node = curr.next       # SAVE
    curr.next = prev            # REWIRE
    prev = curr                 # ADVANCE prev
    curr = next_node            # ADVANCE curr
return prev

Memorize this order: SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR. Swapping any two breaks it.

Hint 5 — Full algorithm + recursive variant

Iterative: as in Hint 4. The loop invariant: at the top of each iteration, prev is the head of the already-reversed prefix, curr points to the next unprocessed node of the original list. When curr is None, all nodes have been processed and prev is the new head.

Recursive: the elegant one-liner expression of the same invariant.

def reverse(head):
    if head is None or head.next is None:
        return head
    new_head = reverse(head.next)   # reverse the rest first
    head.next.next = head           # old second node now points back to head
    head.next = None                # CRITICAL — cut forward link, prevent 2-cycle
    return new_head

Two base cases: empty (head is None) and single node (head.next is None). Forget either and you crash or recurse forever. The line head.next = None is non-obvious; without it you create a cycle and the next traversal hangs.

Time O(N) both versions. Iterative space O(1), recursive space O(N) — and Python’s default recursion limit (1000) makes recursive risky for long lists; use sys.setrecursionlimit(10_000) if you must.