Copy List With Random Pointer

Copying an ordinary linked list is easy: walk it and build new nodes. Now give every node a second pointer, random, that may point at any node in the list — before it, after it, itself — or at None. Copying the values and the next chain is still easy. Copying random is not, because when you copy a node, the copy of its random target may not exist yet.

This problem is a favourite because it has two good answers with a clear trade. The first is a textbook use of a hash map. The second is a clever trick that removes the map. Interviewers usually want the first, then ask for the second.

The problem

Each node has a value, a next pointer and a random pointer that points to any node in the same list or to None. Return a deep copy: a new list of new nodes with the same values, where each copy's next and random point to the corresponding copies. No pointer in the copy may point into the original list.

1class RandomNode:2    """A list node with an extra pointer that may aim anywhere, or at None."""34    def __init__(self, value: int, next_node: "RandomNode | None" = None,5                 random: "RandomNode | None" = None) -> None:6        self.value = value7        self.next = next_node8        self.random = random

Example: a list with values 4 → 8 → 15 → 16, where node 4's random points at node 15, node 8's at node 4, node 15's at None, and node 16's at node 15. The copy has four new nodes with the same values and the same pattern: copy-4's random points at copy-15, and so on.

Constraints: 0 to 10⁵ nodes.

Clarifying questions

• Can random point at the node itself? Yes. The copy's random must then point at the copy itself.
• Can several nodes share a random target? Yes — node 15 is the target of both 4 and 16 above.
• Must the original list be unchanged afterwards? Assume yes. The interleaving method must restore it.
• Empty list? Return None.

Approach 1: copy the chain, then search for each random target

Copy the nodes and the next chain. Then, for each original node, find the position of its random target by walking from the head, and point the copy at the copy in that position.

1def copy_random_list_scan(head: RandomNode | None) -> RandomNode | None:2    """Copy the chain, then find each random target by counting from the head."""3    originals, copies = [], []4    node = head5    while node is not None:6        originals.append(node)7        copies.append(RandomNode(node.value))8        node = node.next9    for a, b in zip(copies, copies[1:]):10        a.next = b11    for i, original in enumerate(originals):12        if original.random is not None:13            j = 014            while originals[j] is not original.random:   # O(n) search per node15                j += 116            copies[i].random = copies[j]17    return copies[0] if copies else None

Time: O(n²). Space: O(n) for the two arrays.

For each of n nodes, the search may walk up to n positions. At 10⁵ nodes that is up to 5 × 10⁹ steps — far too slow. And, as always in this section, the slow part is an inner loop that searches: "where is the copy of this node?"

The key insight

Everything comes down to one question, asked once for next and once for random: given an original node, where is its copy? Answer it in O(1) and the whole copy is O(n).

Two ways to answer it:

• A hash map from original node to copy. Nodes are hashable by identity in Python, so copy_of[node] is an O(1) lookup. Build all the copies first; then every lookup succeeds, even for a random target that comes later in the list.
• Put each copy right after its original. Weave the copies into the original list: 4 → 4' → 8 → 8' → …. Now the copy of any node is simply node.next. No map needed.

Approach 2: a map from original to copy

1def copy_random_list(head: RandomNode | None) -> RandomNode | None:2    """Map every original node to its copy, then wire both pointers."""3    copy_of: dict[RandomNode, RandomNode] = {}4    node = head5    while node is not None:                          # pass 1: make the copies6        copy_of[node] = RandomNode(node.value)7        node = node.next8    node = head9    while node is not None:                          # pass 2: wire them up10        copy_of[node].next = copy_of.get(node.next)11        copy_of[node].random = copy_of.get(node.random)12        node = node.next13    return copy_of.get(head)

copy_of.get(...) instead of copy_of[...] handles None for free: None is never a key, so get returns None, which is exactly the right pointer.

Dry run of pass 2 on the example (pass 1 has created copies 4′, 8′, 15′, 16′):

Node 4's random target (15) comes after it, which is exactly the case that breaks a one-pass copy. Pass 1 made every copy first, so the lookup still works.

Time: O(n) — two passes, O(1) average per lookup. Space: O(n) for the map.

Approach 3: interleave the copies, O(1) extra space

1def copy_random_list_interleaved(head: RandomNode | None) -> RandomNode | None:2    """Weave each copy right after its original. O(1) extra space."""3    if head is None:4        return None5    node = head                                      # pass 1: A A' B B' ...6    while node is not None:7        node.next = RandomNode(node.value, node.next)8        node = node.next.next9    node = head                                      # pass 2: random pointers10    while node is not None:11        if node.random is not None:12            node.next.random = node.random.next      # copy's random = copy of random13        node = node.next.next14    copy_head = head.next                            # pass 3: unweave15    node = head16    while node is not None:17        duplicate = node.next18        node.next = duplicate.next19        duplicate.next = duplicate.next.next if duplicate.next else None20        node = node.next21    return copy_head

After pass 1 the list is 4 → 4′ → 8 → 8′ → 15 → 15′ → 16 → 16′. In pass 2, read node.next.random = node.random.next by naming the parts: node.next is this node's copy, and node.random.next is the copy of this node's random target. For node 4: 4′.random = 15.next = 15′. Pass 3 splits the woven list back into the original and the copy, restoring every original next pointer.

Time: O(n) — three passes. Space: O(1) extra, beyond the n new nodes that are the output. The cost is that it temporarily modifies the input, so it is unsafe if another thread reads the list at the same time.

Which should you lead with? The map version. It is shorter, it never touches the input, and each line has an obvious meaning, so it is hard to get wrong under pressure. Give its complexity, then offer the interleaved version as the answer to "can you do it without the extra memory?" — which is usually the next question. Writing the interleaved version first, without explaining the simpler idea, tends to look memorised rather than understood.

Edge cases

• Empty list: both versions return None.
• A random pointer to the node itself: the map version looks up the node's own copy; the interleaved version sets copy.random = node.next, which is the copy itself. Both correct.
• A random target later in the list: handled because all copies exist before any random pointer is set.
• Checking the result: our tests confirmed three things on 300 random lists — values and pointer patterns match, no copied pointer leads into the original list, and the original list is unchanged afterwards.

Follow-ups

• Clone a graph: the same map from original to copy, filled during a BFS or DFS so each node is copied once, even with cycles. See the Graphs section.
• Copy a binary tree whose nodes have a random pointer: the same two ideas — a map filled in one traversal and wired in a second.
• The input must not be modified, even temporarily: use the map version.