Deep Copy with Random Pointers

July 2026 · 19 min read

Every clone you have written so far walked a list and rebuilt it node by node. That works because a plain list only points forward: by the time you need next, the target is either already built or does not exist yet and never will. Add one more pointer — an arbitrary random that can aim at any node — and that comfortable ordering collapses. This is LeetCode 138, and it is the gateway to a much bigger idea: deep-copying an arbitrary object graph.

The Problem, and Why It Is Genuinely Hard

Each node holds a value, a next pointer, and a random pointer that may point to any node in the list or to nullptr:

class Node {
public:
    int   val;
    Node* next;
    Node* random;
    Node(int v) : val(v), next(nullptr), random(nullptr) {}
};

You must return a deep copy: a brand-new chain of nodes with the same structure, in which no pointer — not one next, not one random — refers back to a node of the original list. If any copied pointer still aims at the input, you have built a shallow copy that shares memory with the source, and mutating one corrupts the other.

Here is the crux. Suppose you walk the list and, at node i, you try to set copy_i->random. Its target might be node i + 5 — a node whose clone does not exist yet. You cannot store the address of a clone you have not allocated, and you cannot store the original's address (that would be shallow). The random pointer creates forward references into a structure you are still constructing. A single forward pass cannot resolve them.

Solution 1: The Hash Map (old → new)

Make the translation explicit. An unordered_map<Node*, Node*> maps each original node to its clone. Pass one allocates every clone and fills the map; pass two, now that every clone exists, wires both pointers by looking up the map:

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    std::unordered_map<Node*, Node*> clone;      // old -> new

    for (Node* p = head; p; p = p->next)          // pass 1: create clones
        clone[p] = new Node(p->val);

    for (Node* p = head; p; p = p->next) {        // pass 2: wire pointers
        clone[p]->next   = clone[p->next];
        clone[p]->random = clone[p->random];
    }
    return clone[head];
}

The subtle line is clone[p->next] when p->next is nullptr. You might expect a crash, but std::unordered_map::operator[] inserts a value-initialised entry for a missing key, and a value-initialised Node* is nullptr. So clone[nullptr] quietly yields nullptr — exactly what you want for the tail and for null randoms — with no explicit guard. It is elegant, but be aware it silently grows the map by one nullptr→nullptr entry.

Complexity: two linear passes, O(n) time, and the map holds one entry per node, O(n) extra space.

The one-pass recursive variant

The same map, viewed as a memo, collapses the two passes into one recursion. The trick that makes it correct is recording the clone before you recurse, so a random (or next) that cycles back to an in-progress node finds the memo instead of recursing forever:

std::unordered_map<Node*, Node*> memo;

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    if (memo.count(head)) return memo[head];     // already cloned

    Node* node = new Node(head->val);
    memo[head] = node;                           // record BEFORE recursing
    node->next   = copyRandomList(head->next);
    node->random = copyRandomList(head->random);
    return node;
}

If you assigned memo[head] after the recursive calls, a list whose random loops back on itself would recurse until the stack overflows. Recording first turns the potential infinite descent into an O(1) map hit. Still O(n) time and O(n) space, now with recursion depth O(n) too — a real risk on long lists.

Solution 2: Interleaving (the O(1)-extra-space weave)

The map costs O(n) memory purely to answer one question: "given an old node, where is its clone?" The interleaving trick answers that question for free by encoding the mapping into the list itself. It runs in three passes.

Pass 1 — weave. Insert each clone directly after its original, so the list becomes A → A' → B → B' → C → C':

for (Node* p = head; p; p = p->next->next) {
    Node* clone = new Node(p->val);
    clone->next = p->next;   // A' -> B
    p->next     = clone;     // A  -> A'
}

Pass 2 — wire the randoms. Now comes the insight that makes the whole method work. After weaving, the clone of any node X is always exactly X->next. The old→new map is no longer a separate structure; it is a single pointer hop encoded in the list's own shape. So if X->random points at some node Y, then the clone's random must point at Y's clone, which is Y->next:

for (Node* p = head; p; p = p->next->next) {
    if (p->random)
        p->next->random = p->random->next;   // clone.random = (X.random).clone
}

Read p->next->random = p->random->next slowly: p->next is the clone of p; p->random is the original target; p->random->next is that target's clone. No lookup, no map, pure pointer arithmetic. The guard if (p->random) matters because nullptr->next would be undefined behaviour.

Pass 3 — unweave, and restore the original. The clones now have correct next and random, but they are still tangled into the input list. You must split the woven chain back into two independent lists. This is not optional politeness: the contract of the problem is that the input list is left untouched, so restoring A → B → C is a required part of the algorithm, not cleanup you can skip.

Node* newHead = head->next;
Node* p = head;          // walks the originals
Node* q = newHead;       // walks the clones
while (p) {
    p->next = p->next->next;                       // restore original next
    q->next = q->next ? q->next->next : nullptr;   // stitch clone next
    p = p->next;
    q = q->next;
}
return newHead;

The ternary on q->next guards the final clone, whose next is the woven nullptr at the very end. Complexity: O(n) time, O(1) extra space beyond the clones you must return — the whole point.

A Full Three-Pass Dry Run

Take three nodes with values 7 → 13 → 11 and randoms 7.random = null, 13.random = 7, 11.random = 13. Trace the woven method pass by pass.

Verify pass 2 against the definition. 13.random is node 7; after weaving, 7's clone is 7->next = 7', so 13'.random = 7' — correct, the copy's random stays entirely inside the copied list. Likewise 11.random = 13 gives 11'.random = 13->next = 13'. No clone points at an original; the deep-copy invariant holds.

Hash Map vs. Weave

The map trades memory for simplicity; the weave trades three careful passes for O(1) space. There is also a hidden constant: std::unordered_map pays a hash, a modulo, and a probable cache miss on every lookup, while the weave's p->next is a single dependent load. On large lists the weave often wins on wall-clock time as well as memory — but it mutates the input mid-flight, which is unacceptable if another thread can observe the list.

The Bigger Idea: This Is Graph Cloning

Strip away the linked-list packaging and this problem is "deep-copy a directed graph." A node with next and random is just a node with two out-edges. The hash-map solution is the general algorithm; the weave is a linked-list-only optimisation that has no analogue for arbitrary graphs.

Clone Graph (LeetCode 133) is the same skeleton with a vector of neighbours instead of two named pointers, solved with DFS and a visited map that doubles as the old→new translation:

Node* cloneGraph(Node* node) {
    std::unordered_map<Node*, Node*> seen;      // old -> new
    std::function<Node*(Node*)> dfs = [&](Node* cur) -> Node* {
        if (!cur) return nullptr;
        if (seen.count(cur)) return seen[cur];   // already cloned
        Node* copy = new Node(cur->val);
        seen[cur] = copy;                        // record BEFORE recursing
        for (Node* nb : cur->neighbors)
            copy->neighbors.push_back(dfs(nb));
        return copy;
    };
    return dfs(node);
}

Notice it is line-for-line the recursive memo from earlier: allocate, record before recursing to break cycles, then recurse on every out-edge. Serialise/deserialise is the third face of the same coin — instead of building clones in memory you write the visited-order to a string and read it back — but the governing idea never changes: assign every node an identity, then rebuild edges against those identities. Master this once and copy-random-list, clone-graph, and deep-copy-any-object-graph are one problem.

Check Yourself

Six situations. Pick the statement that is actually true.

Practice

• LeetCode 138 — Copy List with Random Pointer core implement it both ways; time the map against the weave on a 100k-node list.
• LeetCode 133 — Clone Graph graph the same visited-map idea over arbitrary out-edges.
• LeetCode 138 — variant space re-solve with the strict rule "no extra data structures" to force the interleaving weave.
• LeetCode 1490 — Clone N-ary Tree tree a tree has no cycles, so no visited map is needed — explain why.
• LeetCode 708 — Insert into a Sorted Circular Linked List pointers more pointer surgery under a wrap-around invariant.
• LeetCode 430 — Flatten a Multilevel Doubly Linked List next the sequel: an extra pointer per node, handled by splicing instead of mapping.