Deep Copy List with Random Pointer, in depth: the identity map, the O(1)-space interleaving trick, a copy verifier and graph cloning

Why the obvious copy does not work

Copying a plain linked list is one loop: walk the original, create a node for each value, link each new node to the previous one. Try the same with random pointers and you hit two problems. First, when you copy node B and see that B.random points to node E, the copy of E does not exist yet, because you have not reached it. Second, even when the target does exist, you need to find the copy of a given original, and nodes carry no index or name to look it up by. Pointing B'.random at the original E instead gives a shallow copy: it looks correct when printed but the two lists are tangled, and modifying one corrupts the other.

Values do not help either. Several nodes may hold the same value, so 'find the copy whose value is 11' is ambiguous. The copy must be located by the identity of the original node, not by its contents. Everything below is a way to answer one question quickly: given an original node, where is its copy?

The identity map: two passes

The cleanest answer is a hash map keyed by node identity. The first pass creates a copy of every node and records original -> copy, setting no pointers. The second pass walks the list again; now every target exists, so each copy's next and random are just lookups.

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

def copy_with_map(head):
    """Two passes, O(n) extra space. Keys are nodes, compared by identity."""
    if head is None:
        return None
    clone = {}                                   # original node -> its copy
    cur = head
    while cur:                                   # pass 1: create every copy, no links yet
        clone[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:                                   # pass 2: every target now exists
        clone[cur].next = clone.get(cur.next)    # get(None) -> None handles the tail
        clone[cur].random = clone.get(cur.random)
        cur = cur.next
    return clone[head]

In Python a class without __eq__ hashes by identity, which is exactly what is needed. In Java use IdentityHashMap if the node class overrides equals, since a value-based equality would merge distinct nodes that happen to hold the same value; with the default Object.equals a plain HashMap also works. Time is O(n) and extra space is O(n) for the map, on top of the O(n) the copy itself needs. For how the map behaves internally see hash tables.

One pass with memoisation

The two passes can be merged. Whenever any pointer, next or random, reaches a node that has no copy yet, create the copy on the spot and remember it. When the walk later arrives at that node it finds the copy already made and only fills in its pointers.

def copy_one_pass(head):
    """One pass: create a copy the first time any pointer reaches a node."""
    clone = {None: None}
    def get(node):
        if node not in clone:
            clone[node] = Node(node.val)
        return clone[node]
    cur = head
    while cur:
        c = get(cur)
        c.next = get(cur.next)
        c.random = get(cur.random)
        cur = cur.next
    return clone[head]

Seeding the map with None -> None removes the null checks, and the map doubles as a visited set, exactly as in a memoised graph traversal. A recursive version is also correct but recurses once per node along next, so a 100,000-node list overflows the default stack in Python and Java.

The interleaving trick: O(1) extra space

The map exists only to answer 'where is the copy of X?'. If the copy sat at a location computable from X itself, the map would be unnecessary. The interleaving method makes that happen by temporarily inserting each copy directly after its original, so that the copy of X is simply X.next.

1. Weave. For each original node, create its copy and splice it in right after: A -> A' -> B -> B' -> C -> C'.
2. Set random pointers. For each original X with a non-null random pointer R, the copy of X is X.next and the copy of R is R.next, so set X.next.random = X.random.next.
3. Unweave. Walk the combined list, pointing each original's next past its copy and each copy's next to the following copy. This separates the two lists and restores the original exactly.

static Node copyRandomList(Node head) {
    if (head == null) return null;

    // Pass 1: insert each copy directly after its original. A -> A' -> B -> B' -> ...
    for (Node cur = head; cur != null; cur = cur.next.next) {
        Node copy = new Node(cur.val);
        copy.next = cur.next;
        cur.next = copy;
    }

    // Pass 2: the copy of X is X.next, so copy.random = original.random.next.
    for (Node cur = head; cur != null; cur = cur.next.next) {
        if (cur.random != null) {                 // null guard: random may be absent
            cur.next.random = cur.random.next;
        }
    }

    // Pass 3: unzip into two lists and RESTORE the original's next pointers.
    Node copyHead = head.next;
    for (Node cur = head; cur != null; cur = cur.next) {
        Node copy = cur.next;
        cur.next = copy.next;                     // original skips over its copy again
        copy.next = (copy.next != null) ? copy.next.next : null;
    }
    return copyHead;
}

Pass 2 must finish before pass 3 starts. If you tried to unweave while setting random pointers, a random pointer that points forward would find its target already unwoven, and R.next would no longer be R's copy. Extra space is O(1) beyond the copy itself; time is still O(n), with three passes instead of two.

Worked example

Use the five-node list with values 7, 13, 11, 10, 1, whose random pointers, written as indices, are null, 0, 4, 2, 0. So node 13 points back to 7, node 11 points forward to 1, node 10 points back to 11 and node 1 points back to 7.

After pass 1 the list reads 7 -> 7' -> 13 -> 13' -> 11 -> 11' -> 10 -> 10' -> 1 -> 1'. In pass 2, 7 has no random pointer and is skipped, which is where the null guard matters: without it the Java code dereferences null.next on the first node. For 13, the random is 7, so 13'.random = 7.next = 7'. For 11, the random is 1, a forward pointer, and 1.next is already 1' because pass 1 created every copy. For 10 the random is 11, so it gets 11', and 1 gets 7'.

Pass 3 restores 7 -> 13 -> 11 -> 10 -> 1 and produces 7' -> 13' -> 11' -> 10' -> 1' with randoms null, 0, 4, 2, 0, exactly matching. Three edge cases deserve a test each. The empty list returns null immediately. A single node whose random points to itself: after weaving, A.random.next is A', so the copy points to itself, as it should. A random pointer that points backward, like 10 to 11, works because in pass 2 every copy already exists wherever it is.

Why it is correct

One invariant carries the proof: after pass 1 and until pass 3 begins, for every original X, X.next is the copy of X. Pass 1 establishes it; pass 2 only writes random fields of copies, so it preserves it. Therefore X.next.random = X.random.next sets copy(X).random to copy(X.random), the definition of a correct random pointer. Pass 3 moves each next by exactly one step, restoring the original order and linking the copies in the same order.

Both methods are the same idea, a function from originals to copies; one stores it in a table, the other encodes it in the list's own pointers.

Testing a copy properly

Comparing printed values tells you nothing about the two properties that matter: that no node is shared, and that each random pointer lands on the corresponding copy rather than on the original. The verifier below converts both lists to index form and compares them, and checks identity overlap explicitly.

def verify_copy(orig, copy):
    """True if copy is a deep, structurally identical copy of orig."""
    o_nodes, c_nodes = [], []
    n = orig
    while n:
        o_nodes.append(n); n = n.next
    n = copy
    while n:
        c_nodes.append(n); n = n.next
    if len(o_nodes) != len(c_nodes):
        return False
    if {id(x) for x in o_nodes} & {id(x) for x in c_nodes}:
        return False                                   # shared node: shallow copy
    o_idx = {id(x): i for i, x in enumerate(o_nodes)}
    c_idx = {id(x): i for i, x in enumerate(c_nodes)}
    for o, c in zip(o_nodes, c_nodes):
        if o.val != c.val:
            return False
        o_r = None if o.random is None else o_idx[id(o.random)]
        if c.random is not None and id(c.random) not in c_idx:
            return False                               # random escapes into the original
        c_r = None if c.random is None else c_idx[id(c.random)]
        if o_r != c_r:
            return False
    return True

def build(vals, randoms):
    nodes = [Node(v) for v in vals]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    for node, r in zip(nodes, randoms):
        node.random = None if r is None else nodes[r]
    return nodes[0] if nodes else None

for vals, rnd in [([], []), ([5], [0]), ([7, 13, 11, 10, 1], [None, 0, 4, 2, 0])]:
    head = build(vals, rnd)
    assert head is None or verify_copy(head, copy_with_map(head))

For the interleaving method add one more assertion: after copying, the original list must still verify against a copy of itself taken beforehand, which proves pass 3 restored it. Randomised tests, building lists of random length with random pointers and running all three implementations, catch the ordering and null bugs quickly.

Choosing between the methods

Interleaving's O(1) has a price: during the copy the input is modified, so a concurrent reader sees copies woven into it, and an exception midway leaves the original corrupted. The map methods never touch the input, which is why they are the default outside memory-constrained code.

The same idea, everywhere objects are copied

A linked list with random pointers is a directed graph with at most two outgoing edges per node, and the map method is graph cloning. Replace the while cur walk by a traversal, see BFS and DFS, and the same memo copies an arbitrary graph, including cycles.

Python's copy.deepcopy works the same way: it carries a memo dictionary keyed by id() of each object already copied, so shared references stay shared and cycles terminate. Java serialization keeps a handle table so an object reached twice is written once and restored as one object. Copying garbage collectors leave a forwarding pointer in each moved object, which is the interleaving idea: the location of the copy is stored in the original itself. Cycles in the next chain, which this problem rules out, would need the detection techniques in Floyd's cycle detection.

Failure modes

• Forgetting the null guard. Nodes with no random pointer crash X.random.next.
• Not restoring the original. Returning the copies without pointing each original's next past its copy leaves the input list woven with copies. Many tests only check the output and miss it.
• Unweaving during pass 2. Forward random pointers then read an already-separated list.
• Value-based maps. Keying the map by value, or by a class whose equals compares values, merges distinct nodes with equal values.
• Shallow random pointers. The copy's random points at original nodes. Only an identity-overlap test catches it.
• Deep recursion. A recursive copy overflows the stack on long lists.

The pointer manipulation in pass 3 is the same discipline as in iterative list reversal: save the next pointer before you overwrite it.

What to do next

1. Implement the two-pass map version and the verifier, and run the three edge cases: empty, self-random, backward random.
2. Implement the interleaving version and add the assertion that the original is unchanged afterwards.
3. Write a randomised test that builds 1,000 random lists and checks all your implementations against the verifier.
4. Generalise the one-pass memo to clone an undirected graph given as adjacency lists, using BFS.
5. Read the source of Python's copy module and find where the memo dictionary is consulted and updated.
6. Explain the interleaving invariant aloud in two sentences; if you can, you will reconstruct the algorithm under pressure.