Reverse Linked List

Problem

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

Example: 1→2→3→4→5 → 5→4→3→2→1.

What the interviewer is testing

• Can you manipulate pointers without leaking a node or breaking the chain?
• Can you sketch both iterative and recursive versions on demand?
• Do you handle the empty and single-element cases cleanly?

Iterative solution — O(n) time, O(1) space

Three pointers: prev, curr, next. For each node, remember the next node before you rewire curr.next to point backward. Then advance.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next          # remember before we overwrite
        curr.next = prev          # rewire pointer backward
        prev = curr
        curr = nxt
    return prev

The trick everyone almost gets wrong: save curr.next into a temp before overwriting it. Without that, you lose the rest of the list.

Recursive solution — O(n) time, O(n) stack space

Reverse the tail, then flip the head onto the end.

def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head       # the (now-tail) points back to head
    head.next = None
    return new_head

Complexity — what to say out loud

"Time O(n) — each node is visited once. Space O(1) for the iterative version. Recursive is O(n) stack — a real concern on long lists."

Edge cases the interviewer will ask about

• Empty list — head is null; return null.
• Single-element list — loop runs once, prev becomes that node, returned correctly.
• List with a cycle — undefined by the problem, but worth flagging that reverse on a cyclic list infinite-loops.

Common follow-ups

• "Reverse only nodes between positions m and n." — Walk to position m − 1, reverse the sublist for n − m + 1 steps, splice back in. Dummy head helps.
• "Reverse in groups of k." — Reverse the first k, recursively call on the rest, splice.
• "Detect a cycle before reversing." — Floyd's tortoise and hare in O(n) time, O(1) space.

How to verbalize your answer

"Three-pointer iterative: prev starts at null, curr at head. On each step, save curr.next to a temp so I don't lose the tail, rewire curr.next backward to prev, then advance both. When curr is null, prev is the new head. O(n) time, O(1) space. I can also do it recursively but iterative is safer for long lists."