In-place linked-list reversal ($reverse(P)++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)++Q=S$, with the two reachable node sets disjoint and all payload fields unchanged. Moving $q$ from $Q=q:Q^{\prime }$ 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.