Copy List with Random Pointer (LeetCode 138)

The problem

Each node in a linked list has a val, a next pointer, and a random pointer that can point to any node in the list, or to None. Build a deep copy: a brand-new list of new nodes with the same values, where every next and random in the copy points to the matching copy node, never to an original node. Return the head of the copy.

Input:  node1(val=1) -> node2(val=2)
        node1.random = node2,  node2.random = node2
Output: a new list copy1(1) -> copy2(2)
        copy1.random = copy2,  copy2.random = copy2

The copy has the same shape, but none of its pointers lead back into the original list.

How to think about it

Start with the naive copy. Copying next is easy: walk the list and create a new node for each one. The trouble is random. When you’re copying node 1, its random may point to node 5, whose copy doesn’t exist yet. And even if you search for “the copy with value 7”, values can repeat, so that doesn’t identify a node. A brute force that, for each node, walks the original to find the random target’s index and then walks the copy to the same index is O(n²).

The key insight: separate creating nodes from connecting them, and remember which copy belongs to which original. In a first pass, create a clone of every node and store it in a hash map original -> clone. Now every clone exists. In a second pass, for each original cur, set clone.next = map[cur.next] and clone.random = map[cur.random]. Each lookup is O(1), and identity comes from the node object, not its value.

None needs no special case. m.get(None) returns None, so a missing next or random copies across naturally.

Which pattern is this? A linked-list traversal backed by a hash map. The tell is “deep copy” of a structure with extra pointers: map old nodes to new ones, then re-link. The same idea clones a graph.

Approach

1. If head is None, return None.
2. Pass 1: walk the list; for each node cur, store m[cur] = Node(cur.val).
3. Pass 2: walk again; for each cur, set m[cur].next = m.get(cur.next) and m[cur].random = m.get(cur.random).
4. Return m[head].

Solution

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

def copy_random_list(head):
    if not head: return None
    m = {}                                        # original node -> its clone
    cur = head
    while cur:
        m[cur] = Node(cur.val); cur = cur.next    # pass 1: create every clone
    cur = head
    while cur:
        m[cur].next = m.get(cur.next)             # pass 2: wire clones to clones
        m[cur].random = m.get(cur.random)         # m.get(None) is None
        cur = cur.next
    return m[head]
# a=Node(1); b=Node(2); a.next=b; a.random=b; b.random=b
# copy -> new list where copy.val=1, copy.next.val=2, copy.random.val=2, copy.next.random.val=2

Dry run

On the example (a = node1, b = node2):

Checking the result: copy1.val = 1, copy1.next.val = 2, copy1.random.val = 2, and copy1.random is copy1.next is True, so random points into the new list, not the old one.

Complexity

• Time: O(n). Two linear passes with O(1) dictionary operations.
• Space: O(n). The map holds one entry per node (not counting the output itself). The interleaving trick, which puts each clone right after its original, then splits the lists, brings extra space down to O(1).

Edge cases and pitfalls

• Empty list: returns None.
• random is None: m.get(None) handles it.
• random points to itself (like node2 above): the map returns that node’s own clone, which is correct.
• Keying the map by value. Values can repeat; always key by the node object.
• Returning original nodes. Setting clone.random = cur.random copies a pointer into the old list. The judge checks for this.

Related problems

• Two Sum (LeetCode 1): the same “store it in a map now, look it up in O(1) later” move.
• LRU Cache (LeetCode 146): a hash map pointing into a linked list.
• Serialize and Deserialize Binary Tree (LeetCode 297): rebuilding a pointer structure node by node.