Copy List With Random Pointer: Hash Map vs Interleaving

Copying an ordinary linked list is a warm-up: walk it, make a node for each node, link them in order. Add one extra pointer per node, one that may aim at any node in the list or at nothing, and the warm-up turns into a real question about identity: which new node should a copied pointer aim at?

The problem it solves

Each node has a value, a next pointer and a rand pointer. rand can point forwards, backwards, at the node itself, or be None. Return a deep copy: brand new nodes, the same values, and pointers that mirror the original's shape exactly, but only ever point at new nodes. A copy whose rand points back into the original list is wrong, even if every value looks right.

Values do not identify nodes; two nodes can hold the same value. The only thing that identifies a node is the node itself.

The intuition

The obstacle is order. When you copy node a, its rand may point at c, and the copy of c does not exist yet. You cannot point at a chair you have not drawn.

So separate creating from wiring:

1. Pass one walks the list and creates a bare copy of every node, recording original -> copy in a dictionary.
2. Pass two walks again. Every node now has a twin, so both pointers translate with a lookup: the copy's next is clone[n.next], its rand is clone[n.rand].

Putting None -> None in the dictionary means a missing pointer translates like any other, with no special case.

There is a second, sneakier way to store the same mapping: in the list itself. Weave each copy directly after its original, a -> a' -> b -> b' -> c -> c'. Now the copy of any node x is simply x.next, so a copy's rand is n.rand.next. Unweave at the end and both lists are whole again, with no dictionary at all.

Watch it run

The animation copies a three-node list whose random links aim both forwards and backwards. Pass one lays down three bare twins, value only, and records each in the map. Only when every twin exists does pass two wire next and rand for each, both as lookups. The last frame drops the map: the copy stands alone, the same shape, no shared nodes.

The code

Both versions, with a helper that describes a list as (value, index of rand) pairs so two lists can be compared by shape:

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

def build(vals, rands):
    """rands[i] is the index node i's random link points at, or None."""
    nodes = [Node(v) for v in vals]
    for a, b in zip(nodes, nodes[1:]):
        a.next = b
    for node, r in zip(nodes, rands):
        node.rand = nodes[r] if r is not None else None
    return nodes[0] if nodes else None

def shape(head):
    nodes, n = [], head
    while n:
        nodes.append(n)
        n = n.next
    where = {id(x): i for i, x in enumerate(nodes)}
    return [(x.val, where[id(x.rand)] if x.rand else None) for x in nodes]

def copy_with_map(head):
    clone = {None: None}                     # original node -> its copy
    n = head
    while n:                                 # pass 1: bare copies
        clone[n] = Node(n.val)
        n = n.next
    n = head
    while n:                                 # pass 2: translate both links
        clone[n].next = clone[n.next]
        clone[n].rand = clone[n.rand]
        n = n.next
    return clone[head]

head = build(["a", "b", "c"], [2, 0, None])  # a -> c, b -> a, c -> nothing
copy = copy_with_map(head)
print(shape(copy))                           # [('a', 2), ('b', 0), ('c', None)]
print(copy is head, copy.rand is head.next.next)   # False False

The interleaving version, three passes over the woven list:

def copy_interleaved(head):
    if head is None:
        return None
    n = head
    while n:                                 # 1. weave: a -> a' -> b -> b' -> ...
        twin = Node(n.val)
        twin.next, n.next = n.next, twin
        n = twin.next
    n = head
    while n:                                 # 2. a copy's rand is the original's rand, one step on
        n.next.rand = n.rand.next if n.rand else None
        n = n.next.next
    new_head, n = head.next, head
    while n:                                 # 3. unweave, restoring the original
        twin = n.next
        n.next = twin.next
        twin.next = twin.next.next if twin.next else None
        n = n.next
    return new_head

copy2 = copy_interleaved(head)
print(shape(copy2) == shape(head), shape(head))   # True [('a', 2), ('b', 0), ('c', None)]

Both against Python's own copy.deepcopy, which tracks visited objects and so handles cycles, on 500 random lists with duplicate values. Each check also confirms the copy shares no node with the original and that the original is left unchanged:

import copy as copymod, random

def shares_nodes(a, b):
    seen = set()
    while a:
        seen.add(id(a))
        a = a.next
    while b:
        if id(b) in seen:
            return True
        b = b.next
    return False

random.seed(15)
ok = True
for _ in range(500):
    n = random.randint(0, 12)
    vals = [random.randint(0, 3) for _ in range(n)]
    rands = [random.choice([None] + list(range(n))) for _ in range(n)]
    head = build(vals, rands)
    want = shape(copymod.deepcopy(head))
    for f in (copy_with_map, copy_interleaved):
        c = f(head)
        ok &= shape(c) == want and not shares_nodes(head, c)
    ok &= shape(head) == [(v, r) for v, r in zip(vals, rands)]
print(ok)                                    # True

The complexity

• Hash map: two passes, O(n) time. The dictionary holds n + 1 entries, so O(n) extra space on top of the copy itself.
• Interleaving: three passes, O(n) time, and O(1) extra space; the mapping lives in the next pointers for the duration. The output list is not counted as extra space in either version, since the problem requires it.
• One-pass hash map variant: create a copy on first sight, for next or for rand, whichever comes first. Still O(n) time and space; it saves a walk, not memory.

Where it goes wrong

• Keying the map by value. Two nodes holding 3 collide, and some rand pointers end up at the wrong copy. Key by the node object.
• Pointing into the original. clone[n].rand = n.rand looks right when you print values and is wrong by definition. The random check catches it with shares_nodes.
• Forgetting to unweave. The interleaving version mutates the input while it runs. If step three is skipped or buggy, the caller's list is left corrupted, which is why the test compares the original's shape afterwards.
• Reaching for deepcopy in production. It recurses through next, so a long list overflows the stack: on the Python 3.9 used here, a 400-node list already raised RecursionError.

How to say it in an interview

"The random pointer can aim at a node I haven't copied yet, so I split the work. Pass one creates a bare copy of every node and stores original-to-copy in a hash map, with None mapped to None. Pass two sets each copy's next and rand by looking up the originals' pointers in the map. That's O(n) time and O(n) extra space. If space matters, I can weave each copy right after its original, so a node's copy is its next, set rand as n.rand.next, and unweave, restoring the input: O(1) extra space."

The same "identity, not value" mapping is how graph cloning works, one step up from hash table basics. Pointer rewiring in place is practised in reversing a linked list.