138. Copy List with Random Pointer (Medium)

Problem

A linked list of length n is given where each node contains an extra random pointer that could point to any node in the list, or to null. Construct a deep copy of the list and return its head. The deep copy must consist of entirely new nodes with the same value; the next and random of the new nodes must point to new nodes (never to original nodes).

LeetCode 138 · Link · Medium

Try it yourself

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

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

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, index-based two-pass

First pass: walk the list, store nodes in an array, create a parallel array of new nodes. Second pass: for each original node, find its random’s index, set the new node’s random to the corresponding new node.

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

def copy_random_list(head):
    if not head:
        return None
    originals = []
    copies = []
    cur = head
    while cur:
        originals.append(cur)          # L1: collect originals, O(1) each
        copies.append(Node(cur.val))   # L2: create copies, O(1) each
        cur = cur.next
    idx = {node: i for i, node in enumerate(originals)}  # L3: O(n) index map
    for i, node in enumerate(originals):
        if i + 1 < len(copies):
            copies[i].next = copies[i + 1]      # L4: wire next, O(1)
        if node.random is not None:
            copies[i].random = copies[idx[node.random]]  # L5: wire random, O(1)
    return copies[0]

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

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    const originals: Node[] = [];
    const copies: Node[] = [];
    let cur: Node | null = head;
    while (cur) {
        originals.push(cur);                   // L1: collect originals, O(1) each
        copies.push(new Node(cur.val));        // L2: create copies, O(1) each
        cur = cur.next;
    }
    const idx = new Map<Node, number>(originals.map((n, i) => [n, i]));  // L3: O(n) index map
    for (let i = 0; i < originals.length; i++) {
        if (i + 1 < copies.length) copies[i].next = copies[i + 1];  // L4: wire next
        if (originals[i].random !== null)
            copies[i].random = copies[idx.get(originals[i].random!)!];  // L5: wire random
    }
    return copies[0];
}

final class Solution {
func copyRandomList(_ head: Node?) -> Node? {
        let originals = nodes(head)
        let copies = originals.map { Node($0.val) }
        for index in copies.indices {
            if index + 1 < copies.count {
                copies[index].next = copies[index + 1]
            }
            if let random = originals[index].random,
               let randomIndex = originals.firstIndex(where: { $0 === random }) {
                copies[index].random = copies[randomIndex]
            }
        }
        return copies.first
    }

    private func nodes(_ head: Node?) -> [Node] {
        var result: [Node] = []
        var current = head
        while let node = current {
            result.append(node)
            current = node.next
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1-L2 (collect + copy)	$O(1)$	n	$O(n)$
L3 (build index map)	$O(n)$	1	$O(n)$
L4-L5 (wire pointers)	$O(1)$	n	$O(n)$ ← all phases equal

All phases are $O(n)$ ; the bottleneck is the constant factor from three separate passes. L3 builds the index map in $O(n)$ ; L5 uses it in $O(1)$ per node.

Complexity

Time: $O(n)$ , driven by all three phases equally.
Space: $O(n)$ .

Approach 2: Hash map old → new

Two passes with a dict mapping each original node to its copy. First pass creates copies; second pass wires next and random.

def copy_random_list(head):
    if not head:
        return None
    old_to_new = {}
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)    # L1: O(1) create + store copy
        cur = cur.next
    cur = head
    while cur:
        old_to_new[cur].next = old_to_new.get(cur.next)    # L2: O(1) wire next
        old_to_new[cur].random = old_to_new.get(cur.random) # L3: O(1) wire random
        cur = cur.next
    return old_to_new[head]

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    const oldToNew = new Map<Node, Node>();
    let cur: Node | null = head;
    while (cur) {
        oldToNew.set(cur, new Node(cur.val));  // L1: O(1) create + store copy
        cur = cur.next;
    }
    cur = head;
    while (cur) {
        const copy = oldToNew.get(cur)!;
        copy.next = cur.next ? oldToNew.get(cur.next)! : null;      // L2: O(1) wire next
        copy.random = cur.random ? oldToNew.get(cur.random)! : null; // L3: O(1) wire random
        cur = cur.next;
    }
    return oldToNew.get(head)!;
}

final class Solution {
func copyRandomList(_ head: Node?) -> Node? {
        guard let head else { return nil }
        var copies: [ObjectIdentifier: Node] = [:]
        var current: Node? = head
        while let node = current {
            copies[ObjectIdentifier(node)] = Node(node.val)
            current = node.next
        }
        current = head
        while let node = current {
            let copy = copies[ObjectIdentifier(node)]
            copy?.next = node.next.flatMap { copies[ObjectIdentifier($0)] }
            copy?.random = node.random.flatMap { copies[ObjectIdentifier($0)] }
            current = node.next
        }
        return copies[ObjectIdentifier(head)]
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (create copies)	$O(1)$	n	$O(n)$
L2-L3 (wire pointers)	$O(1)$ each	n each	$O(n)$ ← all phases equal

Two clean passes, each $O(n)$ . No index arithmetic needed: oldToNew.get(cur.random) returns undefined when cur.random is null, handling the null case automatically.

Complexity

Time: $O(n)$ , driven by L1 and L2/L3 equally.
Space: $O(n)$ for the map.

Cleaner than Approach 1; same asymptotics. This is usually the interview-acceptable answer.

Try this approach:

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

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

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

Approach 3: Interwoven nodes (optimal, $O(1)$ extra space)

Three passes, no hash map:

Insert each copy right after its original: A → A' → B → B' → C → C'.
Set each A'.random = A.random.next (the copy of A.random).
Unzip: separate the interwoven lists, restore originals’ next.

def copy_random_list(head):
    if not head:
        return None

    # 1. Interleave copies
    cur = head
    while cur:
        copy = Node(cur.val, cur.next)    # L1: O(1) create interleaved copy
        cur.next = copy
        cur = copy.next

    # 2. Set random pointers on the copies
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next  # L2: O(1) set copy's random
        cur = cur.next.next

    # 3. Split the two interwoven lists apart
    dummy = Node(0)
    copy_tail = dummy
    cur = head
    while cur:
        copy = cur.next
        cur.next = copy.next               # L3: O(1) restore original next
        copy_tail.next = copy              # L4: O(1) link copy list
        copy_tail = copy
        cur = cur.next
    return dummy.next

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;

    // 1. Interleave copies
    let cur: Node | null = head;
    while (cur) {
        const copy = new Node(cur.val, cur.next);  // L1: O(1) create interleaved copy
        cur.next = copy;
        cur = copy.next;
    }

    // 2. Set random pointers on the copies
    cur = head;
    while (cur) {
        if (cur.random) cur.next!.random = cur.random.next;  // L2: O(1) set copy's random
        cur = cur.next!.next;
    }

    // 3. Split the two interwoven lists apart
    const dummy = new Node(0);
    let copyTail: Node = dummy;
    cur = head;
    while (cur) {
        const copy = cur.next!;
        cur.next = copy.next;              // L3: O(1) restore original next
        copyTail.next = copy;             // L4: O(1) link copy list
        copyTail = copy;
        cur = cur.next;
    }
    return dummy.next;
}

final class Solution {
func copyRandomList(_ head: Node?) -> Node? {
        guard let head else { return nil }
        var current: Node? = head
        while let node = current {
            let copy = Node(node.val, node.next)
            node.next = copy
            current = copy.next
        }
        current = head
        while let node = current {
            node.next?.random = node.random?.next
            current = node.next?.next
        }
        let copyHead = head.next
        current = head
        while let node = current {
            let copy = node.next
            node.next = copy?.next
            copy?.next = copy?.next?.next
            current = node.next
        }
        return copyHead
    }
}

Where the time goes, line by line

Variables: n = number of nodes in the list.

Line	Per-call cost	Times executed	Contribution
L1 (interleave)	$O(1)$	n	$O(n)$
L2 (set random)	$O(1)$	n	$O(n)$ ← all three passes equal
L3-L4 (unzip)	$O(1)$	n	$O(n)$

Three $O(n)$ passes; no hash map allocated. The key insight at L2: cur.random.next is precisely the copy of cur.random because every original node is immediately followed by its copy in the interleaved list.

Complexity

Time: $O(n)$ . Three linear passes (L1, L2, L3/L4).
Space: $O(1)$ extra (excluding output).

# Quick smoke tests, paste into a REPL or save as test_138.py and run.
# Uses the hash-map approach (Approach 2).

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

def copy_random_list(head):
    if not head:
        return None
    old_to_new = {}
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        old_to_new[cur].next = old_to_new.get(cur.next)
        old_to_new[cur].random = old_to_new.get(cur.random)
        cur = cur.next
    return old_to_new[head]

def _run_tests():
    # Empty list
    assert copy_random_list(None) is None

    # Single node, random points to itself
    n1 = Node(1)
    n1.random = n1
    copy = copy_random_list(n1)
    assert copy is not n1
    assert copy.val == 1
    assert copy.random is copy  # copy's random points to itself (not original)

    # Two nodes: [[7,None],[13,0]] where 13's random points to node at index 0
    a = Node(7)
    b = Node(13)
    a.next = b
    b.random = a   # index 0
    copy = copy_random_list(a)
    assert copy is not a
    assert copy.val == 7
    assert copy.next.val == 13
    assert copy.next.random is copy  # copy's node 13 random -> copy's node 7

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

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

function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    const oldToNew = new Map<Node, Node>();
    let cur: Node | null = head;
    while (cur) { oldToNew.set(cur, new Node(cur.val)); cur = cur.next; }
    cur = head;
    while (cur) {
        const copy = oldToNew.get(cur)!;
        copy.next = cur.next ? oldToNew.get(cur.next)! : null;
        copy.random = cur.random ? oldToNew.get(cur.random)! : null;
        cur = cur.next;
    }
    return oldToNew.get(head)!;
}

console.assert(copyRandomList(null) === null);

const n1 = new Node(1); n1.random = n1;
const copy1 = copyRandomList(n1);
console.assert(copy1 !== null && copy1 !== n1);
console.assert(copy1!.val === 1);
console.assert(copy1!.random === copy1);

const a = new Node(7); const b = new Node(13);
a.next = b; b.random = a;
const copy2 = copyRandomList(a);
console.assert(copy2 !== null && copy2 !== a);
console.assert(copy2!.val === 7);
console.assert(copy2!.next!.val === 13);
console.assert(copy2!.next!.random === copy2);
console.log("all tests pass");

Summary

Approach	Time	Space	Notes
Index map	$O(n)$	$O(n)$	Straightforward but extra bookkeeping
Hash map old → new	$O(n)$	$O(n)$	Cleanest to write
Interwoven nodes	$O(n)$	$O(1)$	Optimal space; trickier to bookkeep

The hash-map approach is the production-style answer. The interwoven-nodes trick is the canonical “optimize to $O(1)$ extra space” flex.

Linked Lists, two-dimensional pointer graphs
Hash Tables, old-to-new mapping

Hash Map Counting, the lookup table pattern for complements, frequencies, and seen items.
Linked List Pointer Rewiring, the link editing pattern for changing node order without losing the chain.

138. Copy List with Random Pointer (Medium)

Problem

Try it yourself

Approach 1: Brute force, index-based two-pass

Approach 2: Hash map old → new

Approach 3: Interwoven nodes (optimal, O(1)O(1)O(1) extra space)

Test cases

Summary

Related data structures

Related concepts

Approach 3: Interwoven nodes (optimal, $O(1)$ extra space)