Reverse Linked List

Hints

1. Visualise the arrows. Draw the list. Each arrow represents node.next. Reversing the list means flipping every arrow.
2. You need three local variables. Call them prev, curr, and next. prev tracks where the reversed portion ends; curr tracks the next node to flip; next is a temporary so you don't lose the original successor.
3. Save before you overwrite. The line nxt = curr.next must come before curr.next = prev. Otherwise the original curr.next reference is lost forever.
4. Each iteration: save, flip, advance, advance. Save nxt, flip curr.next, advance prev to curr, advance curr to nxt.
5. Return prev, not head. When the loop ends, curr is null and prev is the new head (the old tail). The original head reference still points at what is now the last node.
6. Recursive option. Recurse on head.next, then set head.next.next = head and head.next = None. Elegant but uses O(n) call stack, so the iterative version is preferred in production.

Solution: two approaches

Approach 1 · Iterative: O(n) time, O(1) space

The canonical answer. Three local variables, one loop, no allocation.

def reverse_list(head):
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next            # save the original successor
        curr.next = prev           # flip the arrow
        prev = curr                # advance prev
        curr = nxt                 # advance curr
    return prev                    # the old tail is the new head

Each iteration moves three local variables and rewires one arrow: strict constant work. The loop runs once per node, so the total is O(n). The space cost is the three local variables; no auxiliary data structure.

Why save nxt first: the moment you assign curr.next = prev, the original curr.next pointer is overwritten. If you didn't save it into nxt beforehand, the rest of the list is lost; there is no way to advance curr forward.

Why return prev: at the end of the loop, curr is null (we walked off the end of the original list). prev is the last node we processed, which was the original tail. After all the flips, the original tail's next points to its original predecessor, which points to its predecessor, and so on. The original tail is now the head of the reversed list.

Approach 2 · Recursive: O(n) time, O(n) call stack

Elegant but uses linear stack space. Worth knowing for the structural insight; not the version to ship to production on long lists.

def reverse_list_rec(head):
    if head is None or head.next is None:
        return head                # base case: empty or single node
    new_head = reverse_list_rec(head.next)
    head.next.next = head          # the next node now points back at us
    head.next = None               # we become the new tail
    return new_head

The recursive call returns the new head, but along the way each frame performs the rewiring for its own pair of nodes. The base case returns the original tail (which is the new head). Then each unwound frame sets head.next.next = head, making the recursive call's "current head" point backward to head. The final head.next = None ensures that the eventual new tail terminates correctly.

Complexity comparison

Edge cases to verify

• Empty list: head = None → None. The loop body never executes; prev stays at None.
• Single node: head = 1 → null → 1 → null. The loop runs once: nxt = null, 1.next = null (was already), prev = 1, curr = null. Returns prev = 1.
• Two nodes: 1 → 2 → null → 2 → 1 → null. The smallest non-trivial test; if this works, longer lists work.
• Self-loop input. The problem statement assumes no cycles. If a cycle is present, the iterative version loops forever, production code that must defend against this would need a separate cycle check via Floyd's algorithm.

Where beginners go wrong

• Forgetting nxt = curr.next. The most common bug. You assign curr.next = prev, then try to do curr = curr.next, but curr.next is now prev, so you walk backward instead of forward. The save line is not stylistic; it preserves the only reference to the rest of the list.
• Returning head instead of prev. After the loop, head still points at what is now the last node. The new head is prev. This bug is silent: the function returns a non-null pointer, but to the wrong end of the list.
• Initialising prev = head instead of prev = None. The original head must end up as the new tail with next = None. Initialising prev = head creates a self-loop on the first iteration.
• Trying to swap data instead of pointers. Works for primitive payloads but breaks for any non-trivial node type, breaks for lists with shared nodes, and is two passes (find length, swap from both ends) instead of one. The interview answer is always pointer reversal.
• Recursive without a base case. Forgetting if head is None or head.next is None: return head causes infinite recursion. The base case must handle both the empty list and the single-node list.

Interview follow-ups to expect

• "Reverse the list between positions m and n." See In-Place Reversal Patterns: the same loop, with a dummy head and a count-to-position step before the reversal.
• "Reverse in groups of K." Same loop applied to each K-node window, with stitching between windows. Skip the final group if it has fewer than K nodes.
• "Reverse a doubly linked list." Two pointers per node makes this slightly different: you swap each node's prev and next in place. One traversal; head becomes tail.
• "Check if a list is a palindrome." Reverse the second half (use Floyd's to find the midpoint), then compare with the first half. O(n) time, O(1) memory.
• "Reverse without modifying nodes; return a new reversed list." Allocate fresh nodes during traversal; the original list stays intact. O(n) time and space.

Related reading

• In-Place Reversal Patterns, the deep-dive that exercises this primitive on K-groups and arbitrary ranges.
• Floyd's Tortoise & Hare, the other foundational pointer-discipline drill.
• Linked Lists, the module that frames why this problem matters.