Reverse a Linked List, in depth: the three-pointer loop, its invariant, recursion and the stack limit, sublist and k-group reversal

Why this is harder than reversing an array

Reversing an array is easy because you can index both ends: swap a[i] and a[n-1-i] and walk inward. A singly linked list gives you none of that. You have a pointer to the head, each node holds a value and a next pointer, and the only way to reach node k is to follow k links from the start. There is no way to go backwards.

So instead of moving values, we move arrows. Reversal means that every next pointer should point at the node that used to come before it, the old head should point at nothing, and the old tail should become the head. The values never move, so reversal reorders the list in linear time without allocating or copying a single element.

The danger is equally clear. The moment you overwrite curr.next, you lose your only path to the rest of the list. Every correct reversal is therefore built around one rule: save the successor before you overwrite the pointer to it.

The iterative algorithm: three pointers

The loop keeps three pointers. prev is the head of the part already reversed, initially empty, so None. curr is the head of the part not yet reversed, initially the whole list. nxt is a temporary that remembers curr.next before we destroy it.

class Node:
    __slots__ = ("val", "next")
    def __init__(self, val, next=None):
        self.val, self.next = val, next

def reverse(head):
    prev, curr = None, head
    while curr is not None:
        nxt = curr.next      # 1. remember the rest of the list
        curr.next = prev     # 2. flip one pointer
        prev = curr          # 3. grow the reversed prefix
        curr = nxt           # 4. shrink the unreversed suffix
    return prev              # new head; the old head now points to None

The four statements form a rotation, and their order is not negotiable. Swap steps 1 and 2 and you lose the suffix. Swap steps 3 and 4 and prev becomes the wrong node. Here is the same loop in Java, where the only difference is that null replaces None:

static ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

Worked trace on 1 -> 2 -> 3

Trace the loop by hand once and the algorithm stops being a thing you memorise. Start with prev = None and curr = 1.

The loop ends when curr is None, and prev is node 3, the new head. Notice that the first iteration is what makes the old head the tail: it sets 1.next to the initial prev, which is None. Forgetting that initialisation, for example by starting with prev = head, leaves node 1 pointing at node 2 and node 2 pointing at node 1, a two-node cycle that makes every later traversal loop forever.

Why it is correct: the loop invariant

A loop invariant is a statement that is true before the loop, stays true after every iteration, and together with the exit condition implies the result. For reversal it is: the nodes originally before curr form a correctly reversed list headed by prev, and curr heads the untouched remainder of the original list. Two lists, no shared nodes, nothing lost.

Before the loop the reversed part is empty, prev is None, and curr is the whole list, so it holds. Each iteration detaches exactly one node from the front of the remainder and attaches it to the front of the reversed part, which is precisely how a reversed list grows: the next original node belongs before everything reversed so far. When the loop exits, the remainder is empty, so the reversed part contains every node. Termination is guaranteed because the remainder shrinks by one node each time, provided the input has no cycle.

The cost follows directly. Each node is visited once and each visit does constant work, so time is O(n). The loop uses three pointers regardless of length, so extra space is O(1). If those terms need a refresher, the site's guide to Big-O analysis covers them.

The recursive version, and why it can crash

Recursion expresses reversal as: reverse everything after the head, then append the head to the end of that result. Because the old second node is now the tail of the reversed rest, appending is one assignment.

def reverse_rec(head):
    if head is None or head.next is None:
        return head                  # empty or single node is its own reverse
    new_head = reverse_rec(head.next)
    head.next.next = head            # the node after head now points back to it
    head.next = None                 # head becomes the tail
    return new_head

The line head.next.next = head is the whole trick. After the recursive call, head.next still points at the old second node, which is now the last node of the reversed rest, so pointing its next back at head appends head. Then head.next = None stops head from pointing forward, which would otherwise form a cycle.

The code is elegant and it uses O(n) stack space, one frame per node. That is not a theoretical footnote. CPython's default recursion limit is 1000, so this function raises RecursionError at around a thousand nodes. Java has no fixed depth limit but a fixed thread stack, and with the default stack a list of tens of thousands of nodes typically throws StackOverflowError. Neither CPython nor the JVM eliminates tail calls, and this function is not tail recursive anyway, because work remains after the recursive call returns. Raising the limit with sys.setrecursionlimit moves the cliff rather than removing it and can crash the interpreter outright. Use the recursive version to explain the idea and the iterative version in production. The general trade-off between recursive decomposition and explicit iteration is discussed in divide and conquer.

Reversing a sublist with a dummy node

A common extension is to reverse only positions left through right, leaving the rest intact. Two things make it fiddly: the node before the sublist must be rewired, and when left is 1 there is no node before it. A dummy node placed in front of the head removes that special case, because now every sublist, including one starting at the head, has a predecessor.

def reverse_between(head, left, right):
    """Reverse positions left..right (1-based, inclusive) in one pass."""
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):        # stop on the node before the sublist
        before = before.next
    tail = before.next               # first node of the sublist becomes its tail
    for _ in range(right - left):    # head insertion: move tail.next to the front
        moved = tail.next
        tail.next = moved.next
        moved.next = before.next
        before.next = moved
    return dummy.next

This version uses head insertion instead of the three-pointer loop. before stays fixed and tail stays fixed; each iteration takes the node after tail and moves it to just after before. After right - left moves the sublist is reversed and already stitched to both sides, so there is no separate reconnection step to get wrong. Trace it on 1 -> 2 -> 3 -> 4 -> 5 with left = 2 and right = 4: the list becomes 1 -> 3 -> 2 -> 4 -> 5 and then 1 -> 4 -> 3 -> 2 -> 5.

Reversing in groups of k

Reversing every consecutive group of k nodes, and leaving a final partial group untouched, combines everything so far: a dummy node, a check that a full group exists, the three-pointer loop with a different stopping point, and careful reconnection.

def reverse_k_group(head, k):
    dummy = Node(0, head)
    group_prev = dummy
    while True:
        kth = group_prev
        for _ in range(k):               # is there a full group left?
            kth = kth.next
            if kth is None:
                return dummy.next        # fewer than k nodes remain: leave them
        group_next = kth.next
        prev, curr = group_next, group_prev.next
        while curr is not group_next:    # the plain loop, but ending on group_next
            nxt = curr.next
            curr.next = prev
            prev, curr = curr, nxt
        first = group_prev.next          # old first node is now the group's tail
        group_prev.next = kth
        group_prev = first

Two details carry the correctness. First, prev starts at group_next, not None, so the reversed group's tail is automatically connected to the rest of the list. Second, before overwriting group_prev.next, we remember first, the old first node of the group, because it is now the group's tail and will be the predecessor of the next group. The function is still O(n) time: each node is counted once by the lookahead and flipped once by the loop.

Doubly linked lists

In a doubly linked list each node has prev and next pointers. Reversal is simpler: for every node, swap its two pointers, and the old tail becomes the head. The traversal must follow the pointer that used to be next, which after the swap is stored in prev, a detail that trips people who write curr = curr.next out of habit.

If the list keeps separate head and tail references, as the one inside an LRU cache does, swap those as well, and remember any sentinel nodes. In many real systems you do not reverse a doubly linked list at all: you simply iterate from the tail, which costs nothing. Reversal only earns its keep when the rest of the code expects forward order.

Failure modes and how to test for them

• Lost suffix. Overwriting curr.next before saving it. The list silently shrinks to one node.
• Accidental cycle. Not setting the old head's next to None (wrong initial prev, or missing head.next = None in the recursive version). Printing the list hangs.
• Returning the wrong head. Returning head or curr instead of prev. The caller receives the old head, now the tail, and sees a one-element list.
• Cyclic input. Reversing a list that already contains a cycle never terminates. If input may be untrusted, check with Floyd's cycle detection first; it is also O(n) time and O(1) space.
• Shared nodes. In-place reversal mutates nodes that other references may point to, such as a cached iterator or a second list sharing a tail. If nodes are shared, build a new reversed list instead, at O(n) extra space.

The edge cases are few and fixed: empty list, one node, two nodes, and something long enough to break recursion. A reversal applied twice must give back the original, which is a cheap property to assert. The traversal helper below caps its length so a cycle fails the test instead of hanging it.

def to_list(h):
    out, seen = [], 0
    while h is not None:
        out.append(h.val); h = h.next
        seen += 1
        assert seen < 10_000, "cycle: a next pointer was not flipped"
    return out

def from_list(xs):
    head = None
    for x in reversed(xs):
        head = Node(x, head)
    return head

for xs in ([], [1], [1, 2], [1, 2, 3], list(range(1000))):
    assert to_list(reverse(from_list(xs))) == xs[::-1]
    assert to_list(reverse(reverse(from_list(xs)))) == xs

Trade-offs in real systems

Linked lists are rarely the fastest container on modern hardware: each node is a separate allocation, so a traversal is a chain of dependent loads, while an array streams through the cache. They still matter where nodes must be spliced in constant time or are owned by something else: allocator free lists, cache eviction lists, kernel intrusive lists and the skip list. There, the discipline practised here, save before overwrite and use a sentinel, is what prevents corruption.

What to do next

1. Write the iterative reversal from memory in your main language and state the invariant out loud as you write it.
2. Trace it by hand on a three-node list, filling in a table like the one above, until the order of the four statements feels forced rather than remembered.
3. Run the tests above, including the 1,000-node case, then run the recursive version on 10,000 nodes and watch it fail.
4. Implement reverse_between with a dummy node and test left = 1, left = right and right = n.
5. Implement reverse_k_group and test k = 1, k = n and a list whose length is not a multiple of k.
6. Reverse a doubly linked list with head and tail references and check both directions of traversal afterwards.
7. Combine techniques: check whether a list is a palindrome by finding the middle, reversing the second half, comparing, and restoring it.