Copy List with Random Pointer: Deep Copy with a Hash Map

You are given a linked list where each node has two pointers: next (the usual forward pointer) and random (which can point to any node in the list, or null). Your job is to construct a deep copy of this list. Every node in the copy must be a brand new object, and the next and random pointers in the copy must point to new nodes, not the originals.

This is LeetCode 138: Copy List with Random Pointer, and it is one of the best problems for learning the old-to-new mapping pattern. If you have solved Clone Graph, the core idea will feel familiar. But the linked list version has its own twist: random pointers create cross-links that make a naive copy fail.

Why a naive copy fails

If you try to copy the list in a single pass, you hit a problem. When you create a new node for position 2, its random pointer might need to point to the new node at position 4. But you have not created position 4 yet. You cannot wire up random pointers to nodes that do not exist.

You could try to create nodes and wire next pointers in one pass, then fix up random pointers in a second pass. But how do you find the new node that corresponds to each original node's random target? Searching the new list from the head each time would be O(n) per node, giving O(n^2) total.

The fix is a hash map.

The hash map approach

The idea is simple: use a dictionary that maps each original node to its corresponding new node. This gives you O(1) lookup when you need to wire any pointer.

The algorithm has two passes:

1. First pass: Walk the original list. For each node, create a new node with the same value. Store the mapping original_node -> new_node in the hash map.
2. Second pass: Walk the original list again. For each node, set map[original].next = map[original.next] and map[original].random = map[original.random].

After the second pass, every new node has correct next and random pointers, all pointing to other new nodes. Return map[head].

Python solution

class Node:
    def __init__(self, x: int, next: 'Node | None' = None, random: 'Node | None' = None):
        self.val = int(x)
        self.next = next
        self.random = random

def copy_random_list(head: 'Node | None') -> 'Node | None':
    if not head:
        return None

    old_to_new: dict[Node, Node] = {}

    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next

    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)
        old_to_new[curr].random = old_to_new.get(curr.random)
        curr = curr.next

    return old_to_new[head]

The first while loop creates all new nodes and builds the hash map. The second while loop wires up both pointers. Using dict.get() handles the case where curr.next or curr.random is None, since get() returns None for missing keys.

Visual walkthrough

Let's trace the algorithm on the list [7, 13, 11, 1] where node 13's random points to node 7, node 11's random points to node 1, and node 1's random points to node 7.

The hash map is the entire trick. In the first pass you create all the nodes. In the second pass you wire them up. The map translates any "old node" reference into the corresponding "new node" reference in O(1).

The interleaving approach (O(1) space)

There is a clever alternative that avoids the hash map entirely. Instead of storing the mapping in a dictionary, you interleave the new nodes directly into the original list:

1. For each original node A, create a copy A' and insert it right after A: A -> A' -> B -> B' -> C -> C' -> ...
2. Walk the interleaved list. For each original node A, set A'.random = A.random.next (the copy of A's random target is right after the target).
3. Separate the two lists by restoring the original next pointers and extracting the copy list.

def copy_random_list(head: 'Node | None') -> 'Node | None':
    if not head:
        return None

    curr = head
    while curr:
        copy = Node(curr.val)
        copy.next = curr.next
        curr.next = copy
        curr = copy.next

    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    curr = head
    copy_head = head.next
    while curr:
        copy = curr.next
        curr.next = copy.next
        curr = curr.next
        if curr:
            copy.next = curr.next

    return copy_head

This runs in O(n) time and O(1) extra space (not counting the output). It is more complex to implement correctly, and interviewers are usually happy with the hash map version. But it is worth knowing about, especially if the interviewer asks for a follow-up with reduced space.

Complexity analysis

Time: Both approaches visit each node a constant number of times. The hash map version does two passes, the interleaving version does three. Either way, O(n).

Space: The hash map stores one entry per node, so O(n) extra. The interleaving approach modifies the list in place and uses no extra data structure, so O(1) extra space (the output list itself is required by the problem and does not count).

The building blocks

This problem is built on one core reusable pattern that CodeBricks drills independently.

Old-to-new node mapping

The pattern of creating a parallel data structure by maintaining a dictionary from original objects to their copies:

old_to_new = {}

for node in original_structure:
    old_to_new[node] = create_copy(node)

for node in original_structure:
    wire_pointers(old_to_new, node)

You see this same pattern in:

• Clone Graph (LeetCode 133): map original graph nodes to their clones, then wire neighbors
• Deep copying any structure with cross-references: the hash map is how you resolve "which new object corresponds to this old reference?"

The two-pass structure (create all copies first, wire pointers second) is the key insight. It guarantees that every target node already exists in the map when you need to look it up. No forward-reference problems, no ordering issues.

Edge cases

• Empty list: head is None. Return None immediately. Both solutions handle this with the early return.
• Single node, random is null: one node with random = None. Create one new node, set both pointers to None, return it.
• Single node, random points to itself: one node where random points to itself. The hash map handles this naturally. In the first pass you create the copy. In the second pass, map[node].random = map[node.random] resolves to the copy itself.
• All random pointers are null: the list degenerates into a simple singly linked list. The hash map approach still works, it just sets every random to None.
• All random pointers point to the head: every node's random points to node 0. The map resolves all of them to map[head].

From understanding to recall

You have read through the hash map solution and the interleaving approach. The logic is clear: build a map from old nodes to new nodes, then use it to wire pointers. Two passes, done.

But can you write it cleanly from scratch in five minutes? The details matter. Using the node object (not the value) as the key. Using dict.get() to handle None targets. Remembering to do two separate passes instead of trying to wire pointers on the fly.

Spaced repetition makes these details automatic. You type the two-pass hash map solution from memory at increasing intervals until it flows out without thinking. When a deep copy linked list problem appears in your interview, you do not pause to re-derive the approach. You just write it.

Related posts

• Clone Graph - The graph version of the same old-to-new mapping pattern, using DFS instead of linear traversal
• Reverse Linked List - The foundational linked list manipulation problem, teaching pointer rewiring mechanics

CodeBricks breaks Copy List with Random Pointer into its old-to-new mapping building block and drills it with spaced repetition. You type the pattern from scratch until it is automatic. When a deep copy problem shows up in your interview, you do not think about it. You just write it.