Reversing a Linked List

July 2026 · 20 min read

Reversal is the “hello world” of pointer surgery. It is the most-asked linked-list interview question, and it is the hidden engine inside palindrome checks, list reordering, and k-group reversal. But the real reason to study it is that it is the smallest problem where you must save before you overwrite, state a loop invariant, and reason about termination — the three habits that carry over to every harder list problem. So we will not present the loop; we will derive it, prove it, and only then optimise it.

Why Reversal Is the Archetypal List Problem

Every ingredient of list manipulation shows up in reversal, at minimum scale. There is a destructive pointer write (cur->next = prev). There is the save that must precede it. There is an invariant you can state in one sentence and defend by induction. And there is an in-place transform that runs in O(n) time with O(1) extra space, which is the gold standard the naive approaches will be measured against.

It is also a gateway. Sublist & K-Group Reversal is reversal applied to a window; palindrome detection reverses the second half and walks inward; reorder list reverses the tail and interleaves. If you can derive reversal live, without recalling a memorised sequence of four lines, you can derive all of them. That is the skill this post builds.

Deriving the Three-Pointer Loop

Do not start from the answer. Start from what you want: for each node, its next should point at the node that came before it, instead of the one after. Written directly, that is a single line:

cur->next = prev;   // what we want for the current node

The problem is immediate. The instant you execute that assignment, you have destroyed your only route to the rest of the list — cur->next was the pointer to everything still unprocessed. So the save beat is forced on you: copy the successor before you clobber it.

Node* next = cur->next;   // SAVE the suffix first
cur->next  = prev;        // now the flip is safe

With the flip done, cur is finished — it now heads the reversed portion. Advance: the node we just finished becomes the new prev, and the saved successor becomes the new cur.

prev = cur;
cur  = next;

Wrap it in a loop that runs while cur is non-null, seed prev with nullptr so the original head correctly terminates at null, and return prev — because when the loop ends cur is null and prev is the last node we flipped, i.e. the new head.

Node* reverse(Node* head) {
    Node* prev = nullptr;
    Node* cur  = head;
    while (cur) {
        Node* next = cur->next;   // SAVE
        cur->next  = prev;        // REWIRE
        prev = cur;              // ADVANCE
        cur  = next;             // ADVANCE
    }
    return prev;                 // prev heads the reversed list
}

Three pointers — prev, cur, next — hence the name. Nothing here was invented; every line was forced by the save–rewire–advance discipline from the traversal patterns post.

The Loop Invariant, and Why It Terminates

A loop you can only trace is a loop you will get wrong under pressure. A loop whose invariant you can state, you can reconstruct from scratch. Here it is, exactly:

Prove it by induction on the number of iterations completed.

• Base case. Before the first iteration, prev = nullptr (the reversed prefix is empty) and cur = head (the entire list is untouched). The two chains are disjoint and cover everything. The invariant holds.
• Inductive step. Assume it holds at the top of some iteration. The body saves next (the suffix minus its first node), then flips cur->next = prev, which prepends cur to the reversed prefix; now cur heads a reversed chain one node longer. Then prev = cur and cur = next restore the naming: prev heads the longer reversed prefix, cur heads the shorter suffix. The invariant holds again.
• Termination. Each iteration advances cur one node along a finite list, so after exactly n iterations cur becomes nullptr. At that point the suffix is empty, so by the invariant prev heads the fully reversed list. That is why we return prev, not head: head still names the original first node, which is now the tail.

The whole thing is O(n) time — one visit per node — and O(1) extra space: three pointers, regardless of list length.

Dry Run: Reversing 1→2→3→4

Trace the four pointers explicitly. “List state” shows the reversed prefix on the left of cur and the untouched suffix on the right.

The loop exits because cur == null; we return prev == 4, and the list reads 4→3→2→1. Watch each individual save, rewire, and advance happen below.

Watch One Save / Rewire / Advance at a Time

Five nodes. Every Step performs exactly one micro-operation and names it. The prev, cur, and next tags move; arrows physically flip from green (forward) to orange (backward) the moment a link is rewired.

The Recursive Formulation

The same reversal reads very differently as a recursion. The idea: reverse everything after the head, then fix up the single link between the head and its old successor.

Node* reverse(Node* head) {
    if (!head || !head->next) return head;   // 0 or 1 node: already reversed
    Node* newHead = reverse(head->next);     // reverse the rest first
    head->next->next = head;                  // successor now points back at head
    head->next = nullptr;                     // old head becomes the new tail
    return newHead;                          // deepest node, passed up unchanged
}

The line that trips everyone is head->next->next = head. Read it slowly. The recursive call reversed everything after head but did not touch head own link, so head->next still points at the original successor. After reversal, that successor is the tail of the reversed remainder. We want it to point back at head — that is successor->next = head, and since successor is head->next, we write head->next->next = head. Then head->next = nullptr caps the new end, and newHead (the original last node) rides back up the call stack unchanged.

It is O(n) time, but it costs O(n) stack space — one frame per node. On a few hundred thousand nodes it overflows the stack and crashes, exactly like the recursive destructor from Nodes, Pointers & Memory. Reach for the iterative loop in production; keep the recursion for interviews and for the insight it gives.

Tail-recursive / accumulator version

Carry prev as an accumulator and the recursion becomes structurally identical to the loop — the recursive call is the very last thing the function does:

Node* reverse(Node* cur, Node* prev = nullptr) {
    if (!cur) return prev;
    Node* next = cur->next;
    cur->next = prev;
    return reverse(next, cur);   // tail call: nothing happens after it returns
}

With tail-call optimisation this compiles to O(1) stack. But the C++ standard does not guarantee TCO, so treat this as a bridge concept between the recursive and iterative forms, not a production guarantee. If you need constant stack, write the loop.

Reversing a Doubly Linked List

A doubly linked node carries both prev and next. Reversing the list means every node simply swaps its two link fields; the payloads never move. After the swap, the node reached by the old next is now reached by the new prev, which is how you advance.

Node* reverseDLL(Node* head) {
    Node* cur = head;
    Node* newHead = head;
    while (cur) {
        Node* tmp = cur->prev;   // save
        cur->prev = cur->next;   // swap the two links
        cur->next = tmp;
        newHead = cur;           // the last non-null cur is the new head
        cur = cur->prev;         // advance via what USED to be next
    }
    return newHead;
}

If your list keeps an explicit tail handle alongside head, you can skip tracking newHead and just swap the two handles at the end — the node structure is already reversed. Either way it is O(n) time and O(1) space.

Reversing With a Stack (the naive baseline)

Worth seeing once, so you know what the in-place loop saves you. Push every node, then pop to relink in reverse order:

Node* reverseWithStack(Node* head) {
    std::stack<Node*> st;
    for (Node* p = head; p; p = p->next) st.push(p);
    if (st.empty()) return nullptr;
    Node* newHead = st.top(); st.pop();
    Node* cur = newHead;
    while (!st.empty()) { cur->next = st.top(); st.pop(); cur = cur->next; }
    cur->next = nullptr;   // the old head is now the tail: terminate it
    return newHead;
}

This is O(n) time and O(n) extra space — strictly worse than the three-pointer loop, which achieves the same result with three stack variables. A common variant copies the values into an array and writes them back reversed; that is also O(n) space and only legal when copying values is permitted and cheap. The in-place loop dominates both.

Complexity Across Four Approaches

Three Bugs Everyone Writes Once

Reversal has exactly three classic failure modes, and each maps to one broken beat of save–rewire–advance.

• Returning head instead of prev. After the loop, head still names the original first node — now the tail, with its next set to null. Return it and you get a one-element list. The new head is prev.
• Forgetting to null-terminate the old head. In the recursive version, dropping head->next = nullptr leaves the old head pointing at its old successor while the successor now points back — a two-node cycle (1→2→1) that hangs any later traversal. The iterative loop is immune because prev starts as nullptr and the first flip writes that null into the old head automatically.
• Advancing in the wrong order — the infinite loop. If you write cur->next = prev first and only then try cur = cur->next, you read the link you just overwrote, so cur jumps backward to prev and the loop never terminates. Save next before the rewire and advance from the saved copy.

Check Yourself

Six scenarios drawn from the loop, the invariant, and the classic bugs. Pick the true statement.

Practice

• LeetCode 206 — Reverse Linked List core write it iteratively and recursively; return prev.
• LeetCode 92 — Reverse Linked List II sublist reverse only positions m..n; a dummy head removes the edge cases. See the next post.
• LeetCode 234 — Palindrome Linked List reverse-half find the middle, reverse the second half, walk both inward.
• LeetCode 143 — Reorder List reverse+merge split, reverse the tail, then interleave the two halves.
• LeetCode 25 — Reverse Nodes in k-Group windowed reversal applied to fixed-size windows; check k nodes exist first.
• LeetCode 2130 — Maximum Twin Sum of a Linked List reverse-half reverse the back half and pair it against the front.