Reverse a linked list, one frame at a time

What the stepper shows

• Steps 1–10 change nothing. Five frames pile up and every segment stays grey. The recursion is only travelling to the tail.
• Node 5 is found once. It becomes prev at the deepest call and rides back up through all five returns untouched. That is why return prev is the same value in every frame.
• Each frame changes exactly one link. head->next->next = head flips one segment; head->next = nullptr makes this node the tail. Four frames, four flips.

The leap of faith, precisely

At the moment prev = reverseList(head->next) returns in the frame for node 3, nodes 4 and 5 are already reversed and node 4 is now the tail of that reversed part. Nobody touched node 3's next, so it still points straight at node 4.

You never verify the assumption. You grant it, then do one honest step of work with what it handed you.

Why the base case has two halves

• head == nullptr — the empty list, and the guard that stops head->next from dereferencing null.
• head->next == nullptr — a single node, already reversed. This is the half that produces prev. Remove it and the recursion walks into nullptr, then crashes on head->next->next.

See it in your own debugger

Put a breakpoint on head->next->next = head;, run with F5, and press Continue four times. head->val arrives as 4, then 3, 2, 1 — innermost first, exactly as above.

Cost: O(n) time, one pass. O(n) space, because all n frames are open at the deepest point. The iterative three-pointer version is the O(1)-space answer.