= In-place linked-list reversal
{title2=$reverse(P)\mathbin{++}Q=S$}
Reverse a finite acyclic <linked list> using a reversed-prefix head and an untouched-suffix head. Save the suffix head's old successor, redirect its successor to the prefix, then advance both heads. If $P$ and $Q$ are the current sequences of node identities and $S$ the original sequence, the <loop invariant> is $reverse(P)\mathbin{++}Q=S$, with the two reachable node sets disjoint and all payload fields unchanged. Moving $q$ from $Q=q:Q'$ to $q:P$ preserves this equation. The suffix length decreases, and at exit the prefix is exactly the reversed original list. The method takes linear <running time> and constant <auxiliary space>, reusing the original nodes.
Back to article page
