In iterative linked-list reversal, what invariant holds for prev and curr at each loop top?

## Stating the invariant precisely An invariant is a property that is true before the loop starts, preserved by every iteration, and therefore true when the loop ends. For the three-pointer reversal of a singly linked list, the invariant is: > The original list is partitioned into two chains. `prev` is the head of a fully reversed chain containing the first k nodes of the original order, with the original head at its far end pointing at nothing. `curr` is the head of the remaining n − k nodes, still linked in their original order and untouched. The two chains are disjoint, and their union is exactly the original set of nodes. Before the first iteration, k = 0: `prev` is null (an empty reversed chain) and `curr` is the original head (everything untouched). The invariant holds trivially. ## Why each iteration preserves it The body is `nxt = curr.next; curr.next = prev; prev = curr; curr = nxt`. Take a newest-first notification feed and watch one step. `nxt` names the remainder minus its head, so the untouched chain is safely held. `curr.next = prev` splices `curr` onto the front of the reversed chain — `curr` now points at what was the reversed chain's head, so `curr` is the reversed chain's new head and the chain has k + 1 nodes, still ending at the original head, still ending in null. `prev = curr` records that. `curr = nxt` makes the untouched chain the n − k − 1 remaining nodes. Both chains are still disjoint, their union is unchanged, and k has increased by one: the invariant is restored. That "k increases by one every iteration" clause is the **variant** — the quantity that makes progress — and it is what proves termination. The untouched chain shrinks strictly each pass, so after exactly n iterations it is empty and `curr` is null. ## What the invariant buys you at the end On exit, k = n. The untouched chain is empty and the reversed chain holds all n nodes, headed by `prev`. That is the return value. Candidates who cannot state the invariant routinely return `curr` instead, which is provably null at that point — the invariant turns "which one do I return?" from a guess into a one-line deduction. It also settles a related question people get wrong: the original head is now the tail, and it points at null precisely because `prev` was initialised to null rather than to the head. ## The cost argument, both halves **Time.** Each iteration performs a fixed number of assignments and advances one node. Every node is visited exactly once, so the walk is Θ(n) — and n is a lower bound too, since reversing requires touching every link. **Space.** Auxiliary space is what the algorithm uses *beyond* the input. Here that is three references, independent of n, so O(1). This claim needs two guards. First, it holds because nodes are **relinked in place**; a version that copies values into a temporary buffer and writes them back is O(n) space even though it is also O(n) time. Second, O(1) is a statement about *auxiliary* space — the list itself is still n nodes, and no in-place algorithm pretends otherwise. It is worth naming what O(1) space does *not* claim. It does not say the operation is cheap in wall-clock terms on a long list: n link writes scattered across memory are cache-hostile, and a long linked walk can be markedly slower than a contiguous traversal of the same number of elements even though both are O(n). Asymptotics rank growth, not constants. ## Why interviewers ask for the invariant rather than the code The loop body is four lines that many candidates have memorised. The invariant is what distinguishes memorisation from understanding, and it is the tool that transfers: the same partition idea — one region finished, one region untouched, a boundary that advances by one — is what you state for a partition step, a sliding window, or a segment-wise relink. An interviewer who hears "prev is the reversed part, curr is the rest, and every node is in exactly one of them" knows you can debug the loop when it goes wrong, because you have a checkable statement to test at each step rather than a remembered sequence of assignments. ## Applying the invariant while debugging If a reversal produces a truncated list, print the invariant's two chains after one iteration: a reversed chain of length one and an untouched chain of length n − 1. If the untouched chain is empty after step one, the successor was not saved. If following the reversed chain never terminates, some node points at itself, meaning `prev` was advanced before the flip. The invariant converts a vague "it doesn't work" into a specific violated clause.