206. Reverse Linked List (Easy)

Problem

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

Example

• head = [1,2,3,4,5] → [5,4,3,2,1]
• head = [1,2] → [2,1]
• head = [] → []

LeetCode 206 · Link · Easy

Approach 1: Brute force, collect values, rebuild

Walk the list and store values in an array; build a fresh list in reverse.

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

def reverse_list(head):
    values = []
    cur = head
    while cur:
        values.append(cur.val)    # L1: O(1) per node
        cur = cur.next
    dummy = ListNode()
    tail = dummy
    for v in reversed(values):
        tail.next = ListNode(v)   # L2: O(1) per node, new allocation
        tail = tail.next
    return dummy.next

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (collect)	O(1)	n	O(n) ← dominates
L2 (rebuild in reverse)	O(1)	n	O(n)

Both passes are O(n). The extra O(n) space comes from two sources: the values array and the new list.

Complexity

• Time: O(n), driven by L1 and L2 equally.
• Space: O(n) for the values array + new list.

Correct but wasteful.

Approach 2: Iterative three-pointer reversal (optimal)

Walk the list once, re-pointing each next backward. Needs three pointers: prev, curr, and a scratch next saved before overwriting curr.next.

def reverse_list(head):
    prev, curr = None, head
    while curr:                    # L1: one pass over n nodes
        nxt = curr.next            # L2: O(1) save next
        curr.next = prev           # L3: O(1) reverse pointer
        prev = curr                # L4: O(1) advance prev
        curr = nxt                 # L5: O(1) advance curr
    return prev

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (loop)	O(1)	n	O(n)
L2-L5 (pointer dance)	O(1) each	n	O(n) ← dominates

Four O(1) operations per iteration for exactly n iterations. The canonical interview answer. Memorize the three-pointer dance: it underlies Reverse Nodes in k-Group (25) and Reverse Between (92).

Complexity

• Time: O(n), driven by L2-L5.
• Space: O(1).

Approach 3: Recursive reversal

Recursively reverse the tail, then flip the current node’s link.

def reverse_list(head):
    if not head or not head.next:          # L1: base case
        return head
    new_head = reverse_list(head.next)    # L2: recurse on tail
    head.next.next = head                  # L3: O(1) flip link
    head.next = None                       # L4: O(1) cut old link
    return new_head

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (base case)	O(1)	1	O(1)
L2 (recurse)	O(1) per frame	n	O(n) ← dominates (stack depth)
L3-L4 (flip links)	O(1)	n	O(n)

Each call processes one node and recurses on the rest. Stack depth = n. Python’s default recursion limit (1000) means this can fail on long lists.

Complexity

• Time: O(n), driven by L2 recursion depth.
• Space: O(n) recursion depth.

Elegant but uses stack frames proportional to n, can stack-overflow for very long lists (Python’s default recursion limit is 1000).

Test cases

# Quick smoke tests, paste into a REPL or save as test_206.py and run.
# Uses the iterative three-pointer approach (Approach 2).

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

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

def from_list(vals):
    dummy = ListNode()
    cur = dummy
    for v in vals:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

def _run_tests():
    # Example: [1,2,3,4,5] -> [5,4,3,2,1]
    assert to_list(reverse_list(from_list([1,2,3,4,5]))) == [5,4,3,2,1]
    # Two nodes
    assert to_list(reverse_list(from_list([1,2]))) == [2,1]
    # Single node: no change
    assert to_list(reverse_list(from_list([1]))) == [1]
    # Empty list
    assert reverse_list(None) is None
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

Summary

Approach	Time	Space
Collect + rebuild	O(n)	O(n)
Iterative three-pointer	O(n)	O(1)
Recursive	O(n)	O(n) stack

Related data structures

• Linked Lists, pointer reversal; foundational pattern