linkedlist_reverse

In-place singly-linked-list reversal with three pointers. Algorithm: walk once, and for each node, save $next = curr.next$, flip $curr.next = prev$, then advance $prev = curr$, $curr = next$. After one pass the list is reversed in-place with $O(1)$ extra space. We show the pointer dance on $A \to B \to C \to D \to E$.

Initial: $prev = nil$, $curr = A$ (head), $next = ?$. No node has been reversed yet. The cursor marks $curr$. We keep $prev$ implicit (shown by the color of already-processed nodes turning $good$) because there is no “nil” slot on the list.

Iteration 1, substep a: read $next = curr.next = B$. The link $A \to B$ is highlighted – that's the pointer we are about to flip. Substep b: $curr.next = prev = nil$. In the reversed list $A$ becomes the new tail, so $A.next = nil$.

Iteration 1, substep c: advance. $prev = curr = A$ (now marked $good$, meaning already reversed), $curr = next = B$. $A$ is the tail of the reversed prefix so far. One node reversed: reversed $= [A]$, remaining $= B \to C \to D \to E$.

Iteration 2, substep a: $next = curr.next = C$. Substep b: $curr.next = prev = A$. The link $B \to C$ is being rewritten to $B \to A$. Visually, we show the link $B \to C$ highlighted because that is the original forward pointer we are consuming; once the iteration completes the logical direction is $B \to A$ in the reversed list.

Iteration 2, substep c: advance. $prev = B$, $curr = C$. Reversed so far: $B \to A$, length 2. Remaining: $C \to D \to E$. Two nodes are now coloured $good$ (already in the reversed prefix).

Iteration 3, substep a: $next = curr.next = D$. Substep b: $curr.next = prev = B$. We flip $C \to D$ into $C \to B$ in the reversed list.

Iteration 3, substep c: advance. $prev = C$, $curr = D$. Reversed so far: $C \to B \to A$, length 3. Remaining: $D \to E$. Halfway through (one write per node, $n$ writes total – $O(n)$ time).

Iteration 4, substep a: $next = curr.next = E$. Substep b: $curr.next = prev = C$. Flip $D \to E$ into $D \to C$.

Iteration 4, substep c: advance. $prev = D$, $curr = E$. Reversed so far: $D \to C \to B \to A$, length 4. Remaining: $E$ alone. One more iteration.

Iteration 5, substep a: $next = curr.next = nil$ ($E$ is the original tail). Substep b: $curr.next = prev = D$. Flip to point $E \to D$. Substep c: advance. $prev = E$, $curr = next = nil$, loop exits. The new head is $prev = E$.

Reversal complete. Traversal order from the new head: $E \to D \to C \to B \to A$. Cost: one pass, $O(n)$ time, $O(1)$ auxiliary space (three pointers: $prev$, $curr$, $next$). Scriba's LinkedList primitive doesn't currently expose a per-link direction flip in the DSL, so we trace the pointer moves via cursor and state recolouring; the algorithm itself is faithful frame by frame.