Relationships carry identity. A dictionary translates every original identity into exactly one copied identity.

Deep copying is graph translation. Make one new vertex per old vertex, remember the correspondence, then recreate every edge using copied endpoints.

What the function promises: Return a deep copy of an acyclic next-chain whose random pointers target nodes in that chain or None.

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

def copy_random(head):
    copies = {None: None}
    current = head
    while current is not None:
        copies[current] = RandomNode(current.value)
        current = current.next
    current = head
    while current is not None:
        copies[current].next = copies[current.next]
        copies[current].random = copies[current.random]
        current = current.next
    return copies[head]

a, b = RandomNode(7), RandomNode(7)
a.next, a.random, b.random = b, b, a
clone = copy_random(a)
assert clone is not a and clone.next is not b
assert clone.random is clone.next and clone.next.random is clone

Work and storage: O(n) time and O(n) identity-map space.

When to recognize it: A dictionary translates every original identity into exactly one copied identity.

Check before applying it: Mapping by value fails when values repeat; shallow links leak back into the original structure.

Interleave each copy beside its original, wire random links through neighbors, then carefully separate the two chains.