Reversing a Linked List
Three pointers, four lines, and an ordering that is unforgiving: get the sequence wrong and you either lose the rest of the list or build a node that points at itself. This is the canonical pointer-manipulation exercise precisely because the code is short enough to hold in your head and still easy to get wrong.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
struct Node {
int val;
Node* next;
};
Node* reverseList(Node* head) {
Node* prev = NULL;
Node* cur = head;
while (cur != NULL) {
Node* nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
return prev;
}
int main() {
Node* head = NULL;
for (int i = 5; i >= 1; i--) {
Node* n = new Node();
n->val = i;
n->next = head;
head = n;
}
Node* r = reverseList(head);
while (r != NULL) { cout << r->val << ' '; r = r->next; }
return 0;
}Builds 1 to 5 by prepending, then reverses it iteratively; the loop in main prints 5 4 3 2 1.
How it works, step by step
prev is the reversed part, cur is the rest
At every point the list has been cut in two: everything behind cur already points backwards and is rooted at prev, and everything from cur onward still points forwards. The loop moves one node across that boundary per iteration.
Save next before you destroy it
cur->next = prev overwrites the only reference to the remainder of the list. nxt must be captured first, otherwise the rest of the list is unreachable and leaked the instant you reassign the pointer.
The four lines are a rotation
Read them as: remember where we were going, turn the current arrow around, advance the reversed head, advance the cursor. Every line depends on the one before it, which is why reordering any pair breaks it.
prev starts as NULL for a reason
The original head becomes the new tail, and a tail must point to NULL. Initialising prev to NULL makes the first iteration set that terminator automatically with no special case.
Return prev, not head
When the loop exits, cur is NULL and prev holds the last node processed — the original tail, which is now the head. head still points at the original first node, which is now the tail, so returning it gives you a one-element list.
Complexity
Each node is visited exactly once and only three pointer variables are ever live; the recursive version has the same time complexity but uses O(n) stack space and will overflow on a list of a few hundred thousand nodes.
Common bugs
Reassigning cur->next before saving cur->next
Writing cur->next = prev first and then Node* nxt = cur->next captures prev instead of the real successor. The loop then bounces between two nodes forever or terminates immediately with a two-element list. DryRun draws the nodes and their arrows, so you see cur->next flip to prev and the entire tail simply detach.
Returning head instead of prev
The reversal is correct but you hand back a pointer to what is now the last node, so the caller sees a list of length one. The function compiles, runs, and returns a plausible-looking result, which makes this the most commonly shipped version of the bug.
Creating a self-loop with prev = cur->next
Any variant that sets a node's next to itself turns your traversal into an infinite loop. It usually comes from updating prev and cur in the wrong order, so that prev and cur refer to the same node when the assignment happens. If your print loop never ends, this is why.
Recursing on a long list
The elegant recursive reversal pushes one stack frame per node. At roughly 100,000 nodes you get a stack overflow — a crash with no useful message. Watching the call stack grow linearly makes the limit concrete in a way that the phrase O(n) space does not.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
How do you reverse a linked list?
Walk the list with three pointers: prev (the reversed portion), cur (the node being moved), and a temporary holding cur->next. On each step, save cur->next, point cur->next at prev, then advance prev to cur and cur to the saved node. When cur reaches NULL, prev is the new head.
Why do you need a temporary pointer to reverse a linked list?
Because reversing a node's next pointer destroys the only reference to the rest of the list. Once cur->next is overwritten with prev, there is no way back to the remaining nodes. The temporary captures that successor before it is lost.
Should I reverse a linked list iteratively or recursively?
Iteratively, in almost every real situation. Both are O(n) time, but the iterative version uses O(1) space while the recursive version uses O(n) stack frames and will overflow on long lists. The recursive form is worth knowing as a teaching example, not as production code.
What does the reverse function return?
prev, which after the loop points at the last node processed — the original tail, now the head of the reversed list. Returning the original head is a common mistake and yields a single-node list, since that node's next was set to NULL on the first iteration.