A singly linked node points forward, so reversing a list requires changing links while retaining access to nodes not yet processed. This lesson derives an iterative algorithm and its invariant.
1. Contract and code
Definition 2.2.1
(Contract of in-place list reversal)
Assume head is either NULL or the first node of a finite, acyclic chain of valid, live Node objects. Every next points to the next node in that chain or to NULL. The caller permits this function to mutate every link and ensures there is no concurrent access that conflicts with the mutation. Node values need not be distinct. The function does not allocate, copy or free nodes; it returns the new head. Any existing aliases remain pointers to the same live nodes, but their observed links change. The caller must use the returned pointer as its new head.
#include <stddef.h>
typedef struct Node {
int value;
struct Node *next;
} Node;
Node *reverse_list(Node *head) {
Node *prev = NULL;
Node *cur = head;
while (cur != NULL) {
Node *next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
Saving next must occur before changing cur->next: afterwards that field points backward, so following it no longer reaches the unprocessed suffix. Neither cur nor prev is freed. Ignoring the return value can leave the caller's old head at the tail, unable to reach the rest of the reversed chain.
2. The loop invariant
Write the original sequence of nodes as in their original order. At the start of an iteration after nodes have been processed, where :
prevheads precisely in that order, or isNULLif .curheads precisely in their original order, or isNULLif .- These chains are disjoint, contain all original nodes exactly once, and each ends in
NULL.
Theorem 2.2.2
(Correctness and cost of list reversal)
Let head satisfy the contract, with original nodes and . Then reverse_list(head) returns the first node of a null-terminated chain containing exactly in this order, or NULL if . The loop body runs exactly times, and the function uses auxiliary space and allocates and frees nothing.
Proof
(Initialization, preservation and termination)
Initialization. With , prev is NULL and cur is the original chain. Preservation. If cur is non-null, saving its next pointer keeps the remaining suffix reachable. Redirecting its link to prev puts the next original node at the front of the reversed prefix. Updating both local pointers yields the invariant with . The chains remain disjoint and null-terminated. Termination. Each iteration reduces the length of the unprocessed suffix by one. Since is finite, cur eventually becomes NULL; then and prev heads all original nodes in reverse order, after exactly iterations.
Proof X-ray
Why the invariant must describe both chains
The invariant speaks about both chains at once, and its third clause carries the weight: prev and cur partition the nodes. That partition is what makes the single write cur->next = prev safe. It changes the link of exactly one node, cur, which has just left the unprocessed chain, and the old value of that link was saved in next first. No node of either chain other than cur is touched.
Each hypothesis is used in one place. Finiteness gives termination. Acyclic and null-terminated is used in the base case, where cur must head a chain that ends in NULL. Distinct node identities, not distinct values, give the disjointness clause. The proof closes at : the unprocessed chain is empty, so prev holds every node in reverse. Without acyclicity the base case fails, as the next example shows.
The empty list returns NULL. A one-node list returns the same node, whose link remains NULL. The procedure traverses nodes, so it takes time including the zero-node case as , and uses auxiliary space. Its cost is for this representation and a unit-cost pointer operation model; it says nothing about a differently represented list.
Counterexample mode
A cyclic list is not a long list
A tempting claim is that the loop only walks forward until it meets NULL, so it must also reverse a list that happens to be cyclic. Take nodes and with a->next = b and b->next = a, which violates the contract. Iteration 1: cur = a, next = b, set a->next = NULL, so prev = a, cur = b. Iteration 2: next = b->next = a, set b->next = a, so prev = b, cur = a. Iteration 3: next = a->next = NULL, set a->next = b, so prev = a, cur = NULL. The call returns , but now a->next = b and b->next = a: the returned chain never reaches NULL.
The loop stopped only because the first iteration happened to overwrite a->next with NULL. The postcondition, a null-terminated reversed chain, fails. The repair is the precondition itself: the proof depends on a finite null-terminated chain and makes no claim about invalid input.
3. A pointer trace
Worked example 2.2.3
(Tracing four nodes)
For a list whose successive values are 12 -> 4 -> 15 -> 6 -> NULL, the following table shows the chains at the start of each iteration, followed by the terminal state. Values label nodes here; the proof uses node identities and still works with repeated values.
| Processed | prev chain | cur chain |
|---|---|---|
| 0 | NULL | 12 -> 4 -> 15 -> 6 -> NULL |
| 1 | 12 -> NULL | 4 -> 15 -> 6 -> NULL |
| 2 | 4 -> 12 -> NULL | 15 -> 6 -> NULL |
| 3 | 15 -> 4 -> 12 -> NULL | 6 -> NULL |
| 4 | 6 -> 15 -> 4 -> 12 -> NULL | NULL |
When cur becomes NULL, prev is returned. The original pointer to node 12 still points to that same node, now the tail; it is not a pointer to the whole reversed chain.
Concept lensStructural
Reversal as moving nodes between two stacks
Regard the chain at prev as a stack with its head on top, and the chain at cur as a second stack, also with its head on top. One iteration pops the top node of the cur stack and pushes it onto the prev stack; the only pointer written is the new top's link to the old top. Moving every node from one stack to the other reverses their order, which is the invariant in this language: after moves the prev stack holds on top down to . Moving the nodes back restores the original order, which is why reversing twice returns the original list.
Worked example 2.2.4
(Duplicate values, distinct nodes)
Let the list be p -> q -> r -> NULL, where p and q both hold the value 8 and r holds 3. Iteration 1: next = q, p->next = NULL, prev = p, cur = q. Iteration 2: next = r, q->next = p, prev = q, cur = r. Iteration 3: next = NULL, r->next = q, prev = r, cur = NULL. The call returns r -> q -> p -> NULL, that is, the original third node first, the original second node next, then the original first node. The two nodes holding 8 remain two nodes, in their reversed order; duplicate values do not merge nodes.
Worked example 2.2.5
(Edge cases: the empty list and one node)
For the empty list, cur = head = NULL, so the loop body never runs and the function returns prev, which is NULL. For a single node p, the body runs once: next = NULL, p->next = prev = NULL, prev = p, cur = NULL. The function returns p, whose link is still NULL; reversing a one-node chain changes nothing. These are the cases and of the theorem.
4. Checks and exercises
Common mistake
(Overwriting the link before saving it)
If the loop first wrote cur->next = prev and only then read next = cur->next, then next would equal prev. For 1 -> 2 -> 3 the first iteration would make cur equal NULL, and the function would return node 1 alone, with nodes 2 and 3 unreachable from the result. Another independent alias might happen to retain access to them, but the algorithm cannot rely on one.
Common mistake
(Discarding the returned head)
After reverse_list(head) on 1 -> 2 -> 3, the caller's variable head still points to node 1, which is now the tail and whose next is NULL. Following head shows a list of one node. The new head is the returned pointer, node 3.
Quick check
(Reverse a valid list twice. Why does the returned chain have the original order and the same node identities?)
Apply the theorem to the output of the first call.
Solution · Answer
By the theorem, the first call returns a valid chain , which again satisfies the contract. The second call returns it reversed, . Each call only relinks the existing nodes, without allocation or deallocation, so the same nodes appear in the original order.
Quick check
(Suppose the loop condition were cur->next != NULL instead of cur != NULL. What does the function return for 1 -> 2 -> 3?)
Trace until cur->next is NULL.
Solution · Answer
Iteration 1 (cur is node 1): next is node 2, 1->next = NULL, prev is node 1, cur is node 2. Iteration 2 (cur is node 2, and cur->next is node 3): next is node 3, 2->next = 1, prev is node 2, cur is node 3. Now cur->next is NULL, so the loop stops and the function returns node 2, the chain 2 -> 1 -> NULL. Node 3 was never processed and is missing from the result.
Quick check
(In the trace of 12 -> 4 -> 15 -> 6, what do prev and cur head after two nodes have been processed?)
Use the invariant with .
Solution · Answer
prev heads , which is 4 -> 12 -> NULL, and cur heads , which is 15 -> 6 -> NULL, as in the row for 2 processed nodes.