Linked List Reversal: Turning Each Arrow Round in One Pass

Reversing a linked list in place turns each node's next reference round to point at the node before it, in one pass with three references. The cue is a property of the problem: a linked list has to be reordered, or read from the back, using O(1) extra memory. A linked list is a chain of nodes, each holding a value and next, the reference to the node after it; the last node's next is null, meaning no node. The Linked Lists topic in Data Structures builds one.

The three references are prev, the node already turned round, curr, the node being turned, and next, the node after curr, saved before its arrow changes. Each pass of the loop runs four lines in this order: save next as curr.next, set curr.next to prev, move prev to curr, and move curr to next. The invariant is that the nodes behind curr form a reversed list headed by prev, and the nodes from curr on are untouched. When curr reaches null, prev heads the whole list reversed. The steps follow 7 3 9 5, one node at a time.

prev: null
curr: 7 → 3 → 9 → 5 → null
next: not saved yet

prev: 7 → null
curr: 3 → 9 → 5 → null
next: 3

prev: 3 → 7 → null
curr: 9 → 5 → null
next: 9

prev: 9 → 3 → 7 → null
curr: 5 → null
next: 5

prev: 5 → 9 → 3 → 7 → null
curr: null
next: null

Each step moves one node from the front of curr's list to the front of prev's, and next is what keeps the rest reachable while curr.next is being changed. After four steps curr is null and prev heads 5 9 3 7. The pass is O(n) time for n nodes and O(1) extra space, because only the three references are added; no node is created or copied.

A line of dancers, each with a hand on the shoulder of the one ahead, turning to face the other way works the same way: each dancer turns round and takes the shoulder of the one who was behind, but must first note who was ahead, or the rest of the line is lost. The likeness breaks at what each can see. A dancer can look along the whole line, while the code sees only the three nodes it names, which is why next has to be saved before the arrow turns.