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

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, collect values, rebuild

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

Python

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

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function reverseList(head: ListNode | null): ListNode | null {
    const values: number[] = [];
    let cur = head;
    while (cur) {
        values.push(cur.val);    // L1: O(1) per node
        cur = cur.next;
    }
    const dummy = new ListNode();
    let tail = dummy;
    for (let i = values.length - 1; i >= 0; i--) {
        tail.next = new ListNode(values[i]);  // L2: O(1) per node, new allocation
        tail = tail.next;
    }
    return dummy.next;
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    values := []int{}
    cur := head
    for cur != nil {
        values = append(values, cur.Val) // L1: O(1) per node
        cur = cur.Next
    }
    dummy := &ListNode{}
    tail := dummy
    for i := len(values) - 1; i >= 0; i-- {
        tail.Next = &ListNode{Val: values[i]} // L2: O(1) per node, new allocation
        tail = tail.Next
    }
    return dummy.Next
}

Swift

final class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
        makeList(listValues(head).reversed())
    }
}

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.

Python

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

TypeScript

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;
    while (curr) {                 // L1: one pass over n nodes
        const 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;
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {              // 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
}

Swift

final class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
        var previous: ListNode?
        var current = head
        while let node = current {
            let next = node.next
            node.next = previous
            previous = node
            current = next
        }
        return previous
    }
}

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)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Recursive reversal

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

Python

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

TypeScript

function reverseList(head: ListNode | null): ListNode | null {
    if (!head || !head.next) return head;           // L1: base case
    const newHead = reverseList(head.next);         // L2: recurse on tail
    head.next.next = head;                          // L3: O(1) flip link
    head.next = null;                               // L4: O(1) cut old link
    return newHead;
}

Go

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { // L1: base case
        return head
    }
    newHead := reverseList(head.Next)   // L2: recurse on tail
    head.Next.Next = head               // L3: O(1) flip link
    head.Next = nil                     // L4: O(1) cut old link
    return newHead
}

Swift

final class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
        guard let head, let next = head.next else { return head }
        let reversed = reverseList(next)
        next.next = head
        head.next = nil
        return reversed
    }
}

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).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Test cases

Python

# 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()

TypeScript

class ListNode {
    val: number; next: ListNode | null;
    constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
}

function toList(head: ListNode | null): number[] {
    const out: number[] = [];
    while (head) { out.push(head.val); head = head.next; }
    return out;
}

function fromList(vals: number[]): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    for (const v of vals) { cur.next = new ListNode(v); cur = cur.next; }
    return dummy.next;
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let curr = head;
    while (curr) {
        const nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;
}

console.assert(JSON.stringify(toList(reverseList(fromList([1,2,3,4,5])))) === JSON.stringify([5,4,3,2,1]));
console.assert(JSON.stringify(toList(reverseList(fromList([1,2])))) === JSON.stringify([2,1]));
console.assert(JSON.stringify(toList(reverseList(fromList([1])))) === JSON.stringify([1]));
console.assert(reverseList(null) === null);
console.log("all tests pass");

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

Related concepts

• Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.
• Recursion, the self similar call structure behind subtree, choice tree, and divide problems.