Reverse Linked List

Interview Prep

Warm-upLinked Listlinked-listpointers

The problem

Given the head of a singly linked list, reverse it in place and return the new head. 

class Node:
    def __init__(self, val: int, next: 'Node | None' = None):
        self.val = val
        self.next = next

Pattern: three-pointer in-place flip

A linked list reverses by visiting each node once and flipping its next-pointer to point backward instead of forward. The catch is you have to save the original forward pointer before you overwrite it, otherwise you lose the rest of the list. Three pointers — prev, curr, nxt — is the canonical idiom.

Anywhere a problem asks for "reverse this list" or "reverse a sub-segment of a list" or "is this list a palindrome" (which reduces to reverse-the-second-half), this iterative reverse is the primitive that does the work.

Optimal: iterative, O(1) extra space

def reverse(head: Node | None) -> Node | None:
    prev = None
    curr = head
    while curr is not None:
        nxt = curr.next        # save the next pointer before we overwrite it
        curr.next = prev       # flip curr's pointer to point backward
        prev = curr            # advance prev
        curr = nxt             # advance curr
    return prev                # prev is the new head

Trace

Initial:  1 -> 2 -> 3 -> 4 -> None
prev = None, curr = Node(1)

iter 1:  nxt = Node(2)
         Node(1).next = None       (was Node(2))
         prev = Node(1), curr = Node(2)
         State:  None <- 1    2 -> 3 -> 4 -> None

iter 2:  nxt = Node(3)
         Node(2).next = Node(1)
         prev = Node(2), curr = Node(3)
         State:  None <- 1 <- 2    3 -> 4 -> None

iter 3:  nxt = Node(4)
         Node(3).next = Node(2)
         prev = Node(3), curr = Node(4)
         State:  None <- 1 <- 2 <- 3    4 -> None

iter 4:  nxt = None
         Node(4).next = Node(3)
         prev = Node(4), curr = None
         State:  None <- 1 <- 2 <- 3 <- 4
         Loop exits. return prev = Node(4).

Recursive alternative

Same algorithm expressed via recursion. Each frame reverses the rest of the list, then makes the next node point back to the current. The "head.next.next = head" line is the flip; the explicit head.next = None handles the new tail (caller will fix it for the others). 

def reverse_rec(head: Node | None) -> Node | None:
    if head is None or head.next is None:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head      # the next node should now point back to us
    head.next = None           # and we should point at nothing (will be set by our caller)
    return new_head

Both implementations are O(n) time. The recursive version is O(n) space due to the call stack — on a million-node list it will hit Python's recursion limit, so the iterative version is what you write in production.

Complexity

Variations worth knowing