Swap a pair, trust the rest

Each frame rewires two links, after the recursion has swapped everything behind it.

The leap of faith from LC 206, two nodes at a time. On the way down nothing changes; on the way back up, each frame points its first node at the already-swapped rest, points its second node back at the first, and hands the second node up as the new head.

The list's nodes and next pointers at the current step

original link just rewired rewired this frame's pair ⊥ nullptr

Press Next to make the first call.

Call stack

    LC 24

    Nothing changes on the way down

    Every frame names its pair and immediately calls func on what comes after it. Only when that call returns, with everything behind the pair already swapped, does the frame touch a pointer. The deepest frame finishes first, so the last pair is swapped first and the first pair last.

    Each frame then writes exactly two links: first->next to the head the recursion returned, and second->next back to first. The third link, the one into this pair, belongs to the frame above: it gets written there, from the value this frame returns.

    Trust the call with the rest; fix your own pair; return your new head.

    Why the order of the two lines matters

    Until line 9 runs, secondNode->next is the only pointer to the rest of the list, and line 9 is where it gets read. Swap lines 9 and 10 and secondNode->next would already point back at first: the call would be func(first) again, and the recursion would never end.

    Compared with LC 206

    LC 206 recursed one node on and flipped one link per frame, and every frame returned the same new head, the old tail. LC 24 recurses two nodes on, writes two links per frame, and each frame returns a different head: its own second node. Try the odd list: the 5 is a pair of one, returned unchanged by the base case.