DSA Copying a List with Random Pointers

The problem

Copy List with Random Pointer asks for a deep copy of a linked list whose nodes carry two links. The next link forms the chain as usual. A random link points to any node in the chain, or to None.

A deep copy is a copy built from new nodes, so later edits to the original leave the copy unchanged. The copy must mirror both link patterns using its own nodes. The case below is the one this article tests every solution against.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

head, nodes = build(["A", "B", "C", "D"], [2, 0, 3, None])
for line in describe(head):
    print(line)

Read the lines as the spec. Node A's random link points to C. Node B points back to A, node C points forward to D, and node D points nowhere. A correct clone reproduces these four lines exactly, with clone nodes in every role.

Intuition: copy the chain and borrow the random targets

The first idea copies the chain node by node, which is easy. The random links are the problem. A clone built in one pass meets each random target before its clone exists, so the tempting shortcut points the clone's random link at the original target node.

The shortcut produces the right lines at first glance. It fails the deep-copy test. Editing the original then shows through the clone, because the clone is holding original nodes.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

def copy_borrowing(head):
    clones = {}
    node = head
    while node is not None:
        clones[node] = Node(node.value)
        node = node.next
    node = head
    while node is not None:
        copy_node = clones[node]
        copy_node.next = clones.get(node.next)
        copy_node.random = node.random
        node = node.next
    return clones[head]

head, nodes = build(["A", "B", "C", "D"], [2, 0, 3, None])
clone = copy_borrowing(head)
print("clone before the edit:")
for line in describe(clone):
    print(line)
nodes[0].value = "Z"
print("clone after the original A becomes Z:")
for line in describe(clone):
    print(line)

The clone's second line now reads B random: Z, and the clone was never edited. Its random link landed on an original node. Every clone link must land on a clone, and that rule drives both real solutions below.

Brute force: find each target by its position

The brute force clones the chain first, keeping the original nodes and the clone nodes in two parallel lists. A node's position in its list is its index. For each random link, the brute force finds the original target's index by scanning the original list, then gives the clone the clone node at that same index.

The scans are the cost. A counter records every comparison spent locating targets.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

def clone_by_search(head):
    originals = []
    node = head
    while node is not None:
        originals.append(node)
        node = node.next
    clones = [Node(n.value) for n in originals]
    for i in range(len(clones) - 1):
        clones[i].next = clones[i + 1]
    compared = 0
    for i, original in enumerate(originals):
        if original.random is None:
            continue
        for j, candidate in enumerate(originals):
            compared += 1
            if candidate is original.random:
                clones[i].random = clones[j]
                break
    return (clones[0] if clones else None), compared

head, nodes = build(["A", "B", "C", "D"], [2, 0, 3, None])
clone, compared = clone_by_search(head)
for line in describe(clone):
    print(line)
print("comparisons spent locating targets:", compared)

Eight comparisons located three targets in a four-node chain. Each target can cost a full scan, so the total grows with the square of the chain length. Remembering each target's clone once, instead of searching per link, removes the scans.

The optimal solution: an old-to-new map in two passes

An old-to-new map records the clone built for each original node, and building every clone in a first pass lets a second pass set each clone's links by looking its targets up in the map. That one sentence is the whole method.

The second pass never searches. The clone of any node, whether reached by a next link or a random link, is one map lookup away. A missing key stands for None, which the map lookup returns directly.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

def clone(head):
    if head is None:
        return None
    pairs = {}
    node = head
    while node is not None:
        pairs[node] = Node(node.value)
        node = node.next
    node = head
    while node is not None:
        copy_node = pairs[node]
        copy_node.next = pairs.get(node.next)
        copy_node.random = pairs.get(node.random)
        node = node.next
    return pairs[head]

head, nodes = build(["A", "B", "C", "D"], [2, 0, 3, None])
copy_head = clone(head)
print("clone before the edit:")
for line in describe(copy_head):
    print(line)
nodes[0].value = "Z"
nodes[1].value = "Y"
nodes[0].random = nodes[3]
print("original after the edit:")
for line in describe(head):
    print(line)
print("clone after the edit:")
for line in describe(copy_head):
    print(line)

The clone's lines are identical before and after the edit, while the original's lines changed twice. That stillness is the evidence of a deep copy. A second route weaves each clone directly after its original node and needs no map, trading the map's memory for a more delicate link dance.

Walkthrough: building the map, then wiring the clone

The walk runs the two passes on the article's case and prints the state after each step. The map is printed as value pairs, original value beside clone value, in the order the clones were built.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

head, nodes = build(["A", "B", "C", "D"], [2, 0, 3, None])
pairs = {}
node = head
while node is not None:
    pairs[node] = Node(node.value)
    built = [n.value + "->" + pairs[n].value for n in nodes if n in pairs]
    print("pass one - map now:", built)
    node = node.next
node = head
while node is not None:
    copy_node = pairs[node]
    copy_node.next = pairs.get(node.next)
    copy_node.random = pairs.get(node.random)
    print("pass two - wired clone of", node.value, "- next:", copy_node.next.value if copy_node.next else None, "random:", copy_node.random.value if copy_node.random else None)
    node = node.next
print("finished clone:")
for line in describe(pairs[head]):
    print(line)

Pass one finishes before any link is set, so every target already has a clone when pass two needs it. That ordering is the whole trick. One pass cannot work, because a random link can point forward to a node whose clone does not exist yet.

Complexity

The map copy walks the chain twice, once per pass, so its time is O(n) for n nodes. The position-search copy can scan the whole list for each random link, so its time is O(n squared).

The map holds one entry per node, so its space is O(n). The woven route mentioned above avoids the map and copies in O(1) extra space, at the cost of temporarily tangling the original chain.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

def brute_comparisons(n):
    values = [str(i) for i in range(n)]
    head, nodes = build(values, [n - 1] * n)
    compared = 0
    node = head
    while node is not None:
        target = node.random
        candidate = head
        while candidate is not None:
            compared += 1
            if candidate is target:
                break
            candidate = candidate.next
        node = node.next
    return compared

for n in [4, 8, 16]:
    print("nodes:", n, "worst search comparisons:", brute_comparisons(n), "map pass steps:", 2 * n)

The worst case points every random link at the last node, the most expensive target to find by scanning. At sixteen nodes the search pays 256 comparisons against 32 pass steps. The map turns a search problem into a bookkeeping problem.

Edge cases and pitfalls

A random link that points at the node itself is legal. The map handles it with no special case, because the node's own clone is already in the map when the second pass runs. Pointing the clone at the original self is the borrowing bug from the intuition section, in miniature.

An empty list clones to None. A chain where every random link is None is a plain chain copy, and the same two passes produce it.

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

def build(values, random_indices):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, target in enumerate(random_indices):
        if target is not None:
            nodes[i].random = nodes[target]
    return (nodes[0] if nodes else None), nodes

def describe(head):
    lines = []
    node = head
    while node is not None:
        target = node.random.value if node.random is not None else "None"
        lines.append(node.value + " random: " + target)
        node = node.next
    return lines

def clone(head):
    if head is None:
        return None
    pairs = {}
    node = head
    while node is not None:
        pairs[node] = Node(node.value)
        node = node.next
    node = head
    while node is not None:
        copy_node = pairs[node]
        copy_node.next = pairs.get(node.next)
        copy_node.random = pairs.get(node.random)
        node = node.next
    return pairs[head]

print("empty list clone:", clone(None))
head, nodes = build(["X"], [0])
self_clone = clone(head)
for line in describe(self_clone):
    print("single node, random to itself:", line)
head, nodes = build(["P", "Q"], [None, None])
plain_clone = clone(head)
for line in describe(plain_clone):
    print("no random links:", line)

The self-pointing clone passes the independence test by construction. Its random link is its own clone node, read from the same map as every other link. Uniform wiring, with no branch per link kind, is what keeps the edge cases free.