Copy List with Random Pointer Explained: 7→13→11→10→1 Clone Trace

Imagine you are handed a linked list where every node has two pointers: a standard next pointer and a random pointer that can reference any node in the list or be null. Specifically, consider our working example: nodes are arranged in the exact order 7 $\to$ 13 $\to$ 11 $\to$ 10 $\to$ 1, with random pointers mapping 7 $\to$ null, 13 $\to$ 7, 11 $\to$ 1, 10 $\to$ 11, and 1 $\to$ 7.

If you try to copy this structure using a naive two-pass approach—building the next chain first, then attempting to assign the random pointers—you immediately hit a wall. When you look at the clone of node 13, you know its original random points to node 7. But in your newly allocated list, which node corresponds to 7? Without keeping track of object memory addresses or modifying the structure, you cannot simply look up an arbitrary node in $O(1)$ time.

Trying

When we look at our locked working example of copying the list $\text{7}\to \text{13}\to \text{11}\to \text{10}\to \text{1}$, a standard deep copy fails because a node's $\text{random}$ pointer might reference a node we haven't visited yet, or it might point backward in a way our single pass cannot resolve. To solve this without a secondary $\mathcal{O}(n)$ hash map, we use an interleaved node model that relies entirely on physical structural placement.

Imagine taking our original list and inserting each newly created clone directly adjacent to its original counterpart. For instance, node $\text{7}$ is immediately followed by its clone ${\text{7}}^{\prime }$, which is then followed by original node $\text{13}$, then its clone ${\text{13}}^{\prime }$, and so on. In this interwoven topology, the relationship between an original node and its clone becomes deterministic: if an original node is at pointer $\text{curr}$, its clone is always at $\text{curr.next}$.

This physical proximity solves the $\text{random}$ pointer mystery. If original node $\text{13}$ has a $\text{random}$ pointer targeting original node $\text{7}$, where does clone ${\text{13}}^{\prime }$'s $\text{random}$ pointer need to point? It must point to clone ${\text{7}}^{\prime }$. Since clone ${\text{7}}^{\prime }$ sits immediately after original node $\text{7}$ (meaning at $\text{7.next}$), we can find the exact target for our clone's $\text{random}$ pointer by inspecting $\text{curr.random.next}$.

To see how the interweaving mental model operates in practice, let us trace our locked example: cloning the list $7\to 13\to 11\to 10\to 1$ where the random pointers are given by $7\to \text{null}$, $13\to 7$, $11\to 1$, $10\to 11$, and $1\to 7$.

Given:
- Original nodes in sequence: $7,13,11,10,1$
- Original next pointers: $7\to 13\to 11\to 10\to 1\to \text{null}$
- Original random pointers: $7\to \text{null}$, $13\to 7$, $11\to 1$, $10\to 11$, $1\to 7$

Steps:

- State after Pass 1: $7\to 7^{\prime }\to 13\to 13^{\prime }\to 11\to 11^{\prime }\to 10\to 10^{\prime }\to 1\to 1^{\prime }\to \text{null}$
2. Pass 2: Assign random pointers. For each original node $N$, its clone is $N^{\prime }$. Therefore, $N^{\prime }.\text{random}$ must point to the clone corresponding to $N.\text{random}$. Using our identity formula, $N^{\prime }.\text{random}=N.\text{random}.\text{next}$ (if $N.\text{random}$ is not null).
- For $7^{\prime }$: $7.\text{random}$ is $\text{null}$, so $7^{\prime }.\text{random}=\text{null}$.
- For $13^{\prime }$: $13.\text{random}$ is 7, so $13^{\prime }.\text{random}=7.\text{next}=7^{\prime }$.
- For $11^{\prime }$: $11.\text{random}$ is 1, so $11^{\prime }.\text{random}=1.\text{next}=1^{\prime }$.
- For $10^{\prime }$: $10.\text{random}$ is 11, so $10^{\prime }.\text{random}=11.\text{next}=11^{\prime }$.
- For $1^{\prime }$: $1.\text{random}$ is 7, so $1^{\prime }.\text{random}=7.\text{next}=7^{\prime }$.

- Original list: $7\to 13\to 11\to 10\to 1$
- Cloned list: $7^{\prime }\to 13^{\prime }\to 11^{\prime }\to 10^{\prime }\to 1^{\prime }$

Result:
A fully independent cloned list $7^{\prime }\to 13^{\prime }\to 11^{\prime }\to 10^{\prime }\to 1^{\prime }$ whose random pointers match the expected shape ($7^{\prime }\to \text{null}$, $13^{\prime }\to 7^{\prime }$, $11^{\prime }\to 1^{\prime }$, $10^{\prime }\to 11^{\prime }$, $1^{\prime }\to 7^{\prime }$), completely isolated from the original memory locations.

Try this: Given the intermediate state after Pass 1: 7 -> 7' -> 13 -> 13' -> 11 -> 11' -> 10 -> 10' -> 1 -> 1' -> null, and the original random pointer 10 -> 11, write out the exact pointer assignment expression used in Pass 2 to set 10'.random.

Now that you have seen how the three-pass interweaving algorithm handles the locked sequence of nodes $7\to 13\to 11\to 10\to 1$, it is time to check your mental model of the wiring phase. Recall that Pass 2 is responsible for establishing the random pointers of every cloned node by looking directly at the adjacent original node's random pointer.

Consider the cloned node for 13, let us call it $13^{\prime }$. According to our locked working example, the original node 13 has a random pointer directed at 7. When Pass 2 executes, how do we correctly assign $13^{\prime }.random$ using the interleaved structure where every original node is immediately followed by its clone?

Work through the pointer adjustment for $13^{\prime }$ using the interleaved state formed after Pass 1, keeping in mind how original.random.next reaches the corresponding clone.

Now that you have successfully cloned our locked sequence $7\to 13\to 11\to 10\to 1$ using the three-pass interweaving pattern, let us see how this exact same mental model transfers to a more extreme pointer topology. Imagine you are given a graph where every single node's random pointer creates a strict cycle, such that node $A.\text{random}=A$, or a scenario where all random pointers are null.

By keeping the foundational three-pass procedure intact—interleave clones, wire random pointers via orig.random.next, and unweave—you eliminate the need for any auxiliary hash map storage, keeping space complexity at $O(1)$. When faced with a new pointer-doubling problem in interviews or systems programming, look for whether you can temporarily augment the existing memory layout rather than allocating a separate index dictionary.

Suppose you encounter a variant of our locked list where every node's random pointer points directly to itself instead of pointing to other nodes in the sequence $7\to 13\to 11\to 10\to 1$. Walk through Pass 2 under this self-referential topology: what does clone.random evaluate to when orig.random is orig itself?

def apply_self_loops(head):
    # Pass 1: Interleave
    curr = head
    while curr:
        new_node = Node(curr.val, curr.next, None)
        curr.next = new_node
        curr = new_node.next
    
    # Pass 2: Wire randoms where every node points to itself
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next