Skip to content

069 — Copy List with Random Pointer

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

69 — Copy List with Random Pointer

LeetCode 138 · Medium. A linked list is given where each node contains an additional random pointer, which could point to any node in the list or to nil. Construct a deep copy of the list — the copy must consist of exactly n brand-new nodes, each with its own val, next pointing into the copied list, and random also pointing into the copied list, never back into the original.

🍽️ Intuition

Picture photocopying a chain of sticky notes where each note also has a piece of string tied to some other note in the chain (maybe itself, maybe none). Copying the note itself and its position in the chain is easy — walk down the line and copy each one in order. The hard part is the string: when you copy note 5's string, it points to "the original note 12," but you need your copy of note 5's string to point to your copy of note 12 — and you might not have made that copy yet. You need some way to instantly answer "given an original note, which copy did I make of it?" — that's a lookup problem, not a walking problem.

🚩 Pattern-Recognition Cue

"Deep copy" plus "random pointer that can point anywhere in the list" is the cue. Whenever a copy needs to preserve arbitrary cross-references between nodes (not just the linear next chain), you need a fast way to map "original node" to "its clone" — that's a hash map problem at its core, not a pointer-arithmetic one. Recognize this shape whenever a structure has any pointer besides the one that defines its natural traversal order.

🐢 Brute Force

Two passes with a hash map from original node identity to its clone: first create every clone (values only), then wire up next and random on each clone by looking up the originals' targets in the map.

class Node {
    var val: Int
    var next: Node?
    var random: Node?
    init(_ val: Int) {
        self.val = val
        self.next = nil
        self.random = nil
    }
}

func copyRandomListBruteForce(_ head: Node?) -> Node? {
    guard let head = head else { return nil }

    var map: [ObjectIdentifier: Node] = [:]

    // Pass 1: create every clone, keyed by the original node's identity.
    var curr: Node? = head
    while let node = curr {
        map[ObjectIdentifier(node)] = Node(node.val)
        curr = node.next
    }

    // Pass 2: wire up next and random using the map.
    curr = head
    while let node = curr {
        let clone = map[ObjectIdentifier(node)]
        clone?.next = node.next.flatMap { map[ObjectIdentifier($0)] }
        clone?.random = node.random.flatMap { map[ObjectIdentifier($0)] }
        curr = node.next
    }

    return map[ObjectIdentifier(head)]
}

// smoke test: A(7) -> B(13) -> C(11), A.random = nil, B.random = A, C.random = A
let a = Node(7); let b = Node(13); let c = Node(11)
a.next = b; b.next = c
b.random = a; c.random = a
let clonedA = copyRandomListBruteForce(a)
print(clonedA?.val ?? -1, clonedA?.next?.val ?? -1, clonedA?.next?.next?.val ?? -1)   // 7 13 11
print(clonedA?.random == nil, clonedA?.next?.random === clonedA, clonedA?.next?.next?.random === clonedA)  // true true true
print(clonedA !== a, clonedA?.next !== b)   // true true — genuinely new nodes

Big-O: O(n) time — two linear passes. O(n) extra space for the hash map (in addition to the O(n) for the output copy, which any correct solution needs).

🚀 Optimal

Weave each clone directly after its original (A -> A' -> B -> B' -> ...), use that interleaving to set random pointers in O(1) per node, then un-weave the two lists apart — no hash map required.

func copyRandomList(_ head: Node?) -> Node? {
    guard let head = head else { return nil }

    // 1. Weave: insert each clone directly after its original.
    var curr: Node? = head
    while let node = curr {
        let clone = Node(node.val)
        clone.next = node.next
        node.next = clone
        curr = clone.next
    }

    // 2. Set random pointers on the clones: a node's random clone is always
    //    that random target's very next neighbor (its interleaved copy).
    curr = head
    while let node = curr {
        node.next?.random = node.random?.next
        curr = node.next?.next
    }

    // 3. Unweave: split the interleaved list back into original and clone lists.
    curr = head
    let clonedHead = head.next
    while let node = curr {
        let clone = node.next
        node.next = clone?.next
        clone?.next = clone?.next?.next
        curr = node.next
    }

    return clonedHead
}

// smoke test: A(7) -> B(13) -> C(11), A.random = nil, B.random = A, C.random = A
let x = Node(7); let y = Node(13); let z = Node(11)
x.next = y; y.next = z
y.random = x; z.random = x
let cloned = copyRandomList(x)
print(cloned?.val ?? -1, cloned?.next?.val ?? -1, cloned?.next?.next?.val ?? -1)   // 7 13 11
print(cloned?.random == nil, cloned?.next?.random === cloned, cloned?.next?.next?.random === cloned)  // true true true
print(x.next === y, y.next === z)   // true true — original list is fully restored

// smoke test: single node with a self-loop random pointer
let selfNode = Node(42)
selfNode.random = selfNode
let clonedSelf = copyRandomList(selfNode)
print(clonedSelf?.random === clonedSelf, clonedSelf !== selfNode)   // true true

Big-O: O(n) time — three linear passes (weave, wire randoms, unweave). O(1) extra space beyond the output clones themselves — no hash map needed.

🔑 The Key Insight

This problem leans more on the hash map than on any named traversal pattern — the entire brute force is "remember the original-to-clone mapping so a random pointer copied later can find the right target," which is exactly what a hash map is for. The optimal O(1)-space alternative sidesteps the hash map entirely by using the list's own structure as the lookup table: by physically placing each clone immediately after its original, "the clone of node X" always has a fixed, computable location — X.next — so node.random?.next answers "what's the clone of my random target?" without ever consulting a map. This is the closest fit among the 17 named patterns to paired pointer walking (Two Pointers), since the weave/unweave passes move two logically distinct pointers (original-list pointer and clone-list pointer) through the structure together — but it's a stretch to call it a clean instance of the pattern; the real insight is structural (interleaving), not comparative pointer racing.

🔗 Related Chapters

  • Linked Lists — the underlying data structure, and the source of the O(1) splice/relink operations both approaches depend on.
  • Hash Maps & Hash Sets — the primary technique behind the brute force: original-node-identity to clone-node lookup in O(1) average time.
  • Two Pointers — a stretch here, called out explicitly above; the closest fit among the named patterns is the paired original/clone pointer walking in the weave-and-unweave optimal approach.

🧸 Memory Sentence

Copy List with Random Pointer is photocopying sticky notes with strings attached — either keep a lookup table of "original note → its copy," or copy each note right next to its original so the copy's address is always one step away.

✅ Check Your Understanding

In the optimal weaving approach, step 2 sets node.next?.random = node.random?.next. Explain in your own words why node.random?.next is guaranteed to be the clone of node.random, and not some unrelated node — what invariant does step 1 (the weave) establish that makes this true for every node, including one whose random is nil?

⬅️ Previous: Remove Nth Node From End of List · Next: Add Two Numbers ➡️

Clone this wiki locally