206 - Reverse Linked List

Difficulty: Easy | Pattern: Iterative / Recursive Linked List | Company tags: Amazon, Google, Apple, Microsoft

Problem Statement

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

Example 1:

Input:  1 → 2 → 3 → 4 → 5 → null
Output: 5 → 4 → 3 → 2 → 1 → null

Example 2:

Input:  1 → 2 → null
Output: 2 → 1 → null

Example 3:

Input:  null
Output: null

Approach 1: Iterative (Most Common in Interviews)

Key insight: Walk through the list with three pointers — prev, curr, next. At each step, redirect curr.next to prev, then advance all three pointers.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # save next before overwriting
        curr.next = prev       # reverse the link
        prev = curr            # advance prev
        curr = next_node       # advance curr
    return prev  # prev is now the new head

Algorithm Flow

Dry Run (Iterative)

1 → 2 → 3 → null

Step	prev	curr	curr.next (before)	curr.next (after)
Start	null	1	2	—
1	null	1	2	null
2	1	2	3	1
3	2	3	null	2
End	3	null	—	—

Return prev = 3 → list is now 3 → 2 → 1 → null ✓

Approach 2: Recursive

Key insight: Recursively reverse the rest of the list, then attach the current node at the end.

def reverseList(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head
    
    # Reverse the rest
    new_head = reverseList(head.next)
    
    # Attach current node at end of reversed list
    head.next.next = head
    head.next = None
    
    return new_head

Recursive dry run on 1 → 2 → 3:

1. reverseList(1) calls reverseList(2)
2. reverseList(2) calls reverseList(3)
3. reverseList(3) returns 3 (base case, 3.next = null)
4. Back in frame 2: 3.next = 2, 2.next = null → 3 → 2; return 3
5. Back in frame 1: 2.next = 1, 1.next = null → 3 → 2 → 1; return 3

Edge Cases

• Empty list (head = null) → return null
• Single node → return it unchanged
• Two nodes: 1 → 2 → 2 → 1

Complexity

Approach	Time	Space
Iterative	O(n)	O(1)
Recursive	O(n)	O(n) call stack

Prefer iterative in interviews to avoid stack overflow risk on very long lists.

Key Terms

Term	Definition (in context of this problem)
Three-pointer technique	prev, curr, and next_node track the reversed portion, the current node, and the unreversed remainder respectively.
In-place reversal	The list is reversed by rewiring .next pointers of existing nodes, without allocating new nodes — O(1) extra space.
Tail recursion pitfall	The recursive approach isn't tail-recursive in Python (the pointer fix happens after the recursive call returns), so it still uses O(n) stack frames.
Base case	For recursion, an empty list or single node is already "reversed," anchoring the recursive unwinding.

FAQ

1. Can this be solved without extra space? Yes — the iterative approach uses O(1) extra space since it only rewires existing node pointers with three local variables. The recursive approach uses O(n) space due to the call stack.
2. What if the input list is empty? head is None, the while loop (or the recursive base case) never executes/triggers immediately, and the function returns None, which is correct.
3. How would this change for a doubly linked list? You'd need to swap .next and .prev for every node in addition to redirecting .next, and the new head is still the old tail.
4. What's the common follow-up interviewers ask? "Reverse only a sublist between positions m and n" (LeetCode 92) or "reverse nodes in k-group" (LeetCode 25), both building on the same three-pointer rewiring technique applied to a bounded segment.
5. Why is iterative preferred over recursive in interviews? Recursive reversal risks stack overflow on very long lists (e.g., 10,000+ nodes) since each call consumes a stack frame, whereas iterative reversal runs in constant space regardless of list length.

Quick Revision

• Goal: reverse a singly linked list in place and return the new head.
• Iterative: maintain prev, curr, next_node; at each step save curr.next, rewire curr.next = prev, then advance both prev and curr.
• Loop ends when curr is None; prev is the new head.
• Recursive: recurse to the end first, then on the way back set head.next.next = head and head.next = None.
• Recursive base case: empty list or single node returns itself unchanged.
• Iterative is O(n) time, O(1) space; recursive is O(n) time, O(n) space (call stack).
• Prefer iterative in interviews — no stack overflow risk on long lists.
• Classic pitfall: forgetting to save curr.next before overwriting it, which loses the rest of the list.

Related Problems

• 234-PalindromeLinkedList — uses reversal of the second half as a subroutine.
• 142-LinkedListCycleII — same linked-list pointer-manipulation family (fast/slow pointers).
• 21-MergeTwoSortedLists — related linked-list rewiring pattern.
• LeetCode 92 (Reverse Linked List II) and LeetCode 25 (Reverse Nodes in k-Group) — direct extensions of this exact technique; not in this directory.