In-Place Reversal Patterns

Why every linked-list interview lands here

Linked-list reversal is the canonical pointer-discipline drill. It tests three things at once: whether you can reason about reference semantics (assigning a pointer doesn't copy a node), whether you can hold a temporary correctly (the next rescue), and whether you can write the final assignment that returns the new head (which is prev, not curr).

Once the pattern is internalised, every variant (reverse in K-groups, reverse between two indices, reverse alternate K-groups) becomes a small composition of the same primitive. The variants don't need new ideas; they need careful boundary stitching.

The primitive, reverse the whole list

Let's nail the core loop first. Given the head of a linked list, return a new head that traverses the list in reverse order.

def reverse(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next            # save: we're about to overwrite curr.next
        curr.next = prev           # flip: the arrow now points backward
        prev = curr                # advance prev
        curr = nxt                 # advance curr
    return prev                    # new head - the old tail

Trace it on a three-node list 1 → 2 → 3 → null. Initially prev = null, curr = 1.

iter 1: nxt = 2; 1.next = null; prev = 1; curr = 2
        list: null ← 1     2 → 3 → null

iter 2: nxt = 3; 2.next = 1; prev = 2; curr = 3
        list: null ← 1 ← 2     3 → null

iter 3: nxt = null; 3.next = 2; prev = 3; curr = null
        list: null ← 1 ← 2 ← 3

return prev → 3 (the new head)

O(n) time, O(1) extra memory. Anything more elaborate is overcomplicating. Memorise the four lines and the four-line argument for why each is necessary.

The recursive version

Worth knowing because the structure is elegant; not the version to write first in an interview because the call stack is O(n).

def reverse_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)   # recurse first
    head.next.next = head               # the next node now points back at us
    head.next = None                    # we become the new tail
    return new_head

The line that earns its keep is head.next.next = head. At that moment, head.next is the original successor, which the recursive call has already turned into the second-to-last node of the reversed sublist. We set its next to head, hooking the current node onto the back. Then we null out head.next so the new tail terminates correctly. Use the iterative version unless you specifically need the recursive structure for a related problem.

Variant, reverse in K-groups

Given a list and an integer K, reverse every consecutive group of K nodes. If the final group has fewer than K nodes, leave it as-is.

The technique is to walk K nodes ahead, check that K nodes are actually available, then reverse the K-node segment in place using the primitive above. The hard part is stitching: the previous group's tail must point to the reversed group's new head, and the reversed group's new tail must point to the next group's head.

def reverse_k_group(head, k):
    dummy = Node(0)
    dummy.next = head
    group_prev = dummy

    while True:
        # Step 1: locate the kth node from group_prev. If we run out, stop.
        kth = group_prev
        for _ in range(k):
            kth = kth.next
            if kth is None:
                return dummy.next

        # Step 2: reverse the segment [group_prev.next .. kth].
        group_next = kth.next            # save the tail's successor
        prev = group_next                # so reversed-tail points to it
        curr = group_prev.next
        while curr is not group_next:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        # Step 3: stitch - the new head of this group is `kth`.
        new_tail = group_prev.next       # was the head; is now the tail
        group_prev.next = kth            # link previous group to new head
        group_prev = new_tail            # advance the boundary

Two design choices justify a sentence each. The dummy head means we never special-case the very first group, group_prev always exists. Initialising prev = group_next means the reversed segment's last next assignment naturally points to whatever followed the group, eliminating a separate stitching step. Both are small but make the code shorter and less bug-prone.

Complexity: each node is visited once during the count and once during the reversal. O(n) total, O(1) extra memory.

Variant, reverse between positions m and n

Given m and n (1-indexed positions, m ≤ n), reverse the sublist from position m to position n in place.

def reverse_between(head, m, n):
    if m == n:
        return head
    dummy = Node(0)
    dummy.next = head
    before = dummy
    for _ in range(m - 1):
        before = before.next            # before = node at position m-1

    # The classic in-place K-step reversal, but only n-m+1 nodes.
    prev = None
    curr = before.next
    for _ in range(n - m + 1):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # Stitch - `before.next` was the original head of the segment;
    # it is now the tail and must point to `curr` (the node after the segment).
    before.next.next = curr
    before.next = prev
    return dummy.next

The dummy head makes m = 1 work without a special case. The "stitch" at the end is two lines because we need to wire both ends of the reversed segment to the surrounding list. Read it as: "the original head of the segment is now its tail and points to whatever followed; the node before the segment now points to the new head."

Complexity, reasoned

All three variants run in O(n) time and O(1) extra memory. The recursive variant uses O(n) call stack, strictly worse on memory and a real problem on lists with millions of nodes. Iterative pointer reversal is the production version; recursion is the academic one.

When to reach for in-place reversal

Whenever a problem asks you to "reverse" something in a linked list, this primitive is the answer. The problem might dress it up as "swap pairs" (K=2 reversal), "rotate by K positions" (find the new tail, split, swap the pieces), or "is this list a palindrome?" (reverse the second half, compare). All of them lean on this loop. Internalise the four lines and the variants are quick.

Where beginners go wrong

• Forgetting to save nxt = curr.next. Once you reassign curr.next = prev, the original successor is unreachable. The save is the algorithm's whole reason for being.
• Returning head instead of prev. After the loop, curr is null and head still points to the (now last) node. The new head is prev.
• Trying to swap data instead of pointers. Works for primitives but fails the moment node payloads are non-trivial (objects, references). The interview answer is always to reverse pointers.
• Reversing K-groups without a dummy head. The first group's stitching becomes a special case ("if this is the first group, set head = …"), error-prone. The dummy head removes the special case entirely.
• Off-by-one in the K-group counting loop. The for _ in range(k) should advance kth exactly K steps from group_prev, leaving kth at the K-th node of the group. If you start kth = group_prev.next instead and loop K-1 times, you're equivalent, but mixing conventions causes bugs.

What to read next

Floyd's Tortoise & Hare is the next pointer-discipline classic, fast/slow pointers detecting and locating cycles in O(1) memory. The Linked Lists module ties both concepts together and adds merge, partition, and the LRU pattern.