Copy List With Random Pointer

Difficulty: Medium Source: NeetCode

Problem

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null. Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers represent the same list state. None of the pointers in the new list should point to nodes in the original list. Return the head of the copied linked list.

Example 1: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2: Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Constraints:

• 0 <= n <= 1000
• -10^4 <= Node.val <= 10^4
• Node.random is null or pointing to some node in the linked list

Prerequisites

Before attempting this problem, you should be comfortable with:

• Hash Maps — mapping old nodes to their new copies for O(1) lookup
• Two-Pass Traversal — first create nodes, then wire up pointers
• Deep vs Shallow Copy — understanding that pointers must point to new nodes, not original ones

1. Hash Map Approach (Standard)

Intuition

The challenge here is the random pointer — it can point anywhere in the list, including backwards. If we try to copy in one pass, we might reference a copy that doesn’t exist yet.

The clean solution: two passes using a hash map that maps each original node to its newly created copy.

• Pass 1: Walk the original list and create a fresh copy of each node, storing the mapping {original: copy}.
• Pass 2: Walk again and wire up .next and .random for each copy using the map.

Since the map gives us copy_of[original.next] and copy_of[original.random] in O(1), this is efficient.

Algorithm

1. Edge case: if head is None, return None.
2. Create a dictionary old_to_new = {}.
3. First pass — create all copy nodes: for each node in the original list, create new_node = Node(node.val) and store old_to_new[node] = new_node.
4. Second pass — wire pointers: for each node in the original list:
   • old_to_new[node].next = old_to_new.get(node.next)
   • old_to_new[node].random = old_to_new.get(node.random)
5. Return old_to_new[head].

Solution

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

def build_list(pairs):
    """Build list from [(val, random_index_or_None), ...]"""
    if not pairs:
        return None
    nodes = [Node(val) for val, _ in pairs]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, (_, rand_idx) in enumerate(pairs):
        if rand_idx is not None:
            nodes[i].random = nodes[rand_idx]
    return nodes[0]

def print_list(head):
    # Build node->index mapping to display random pointer indices
    node_index = {}
    cur = head
    idx = 0
    while cur:
        node_index[cur] = idx
        cur = cur.next
        idx += 1
    cur = head
    result = []
    while cur:
        rand_idx = node_index[cur.random] if cur.random else None
        result.append(f"[{cur.val}, {rand_idx}]")
        cur = cur.next
    print(" -> ".join(result) if result else "None")

def copyRandomList(head):
    if not head:
        return None

    old_to_new = {}

    # Pass 1: create all copy nodes
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next

    # Pass 2: wire up next and random pointers
    cur = head
    while cur:
        if cur.next:
            old_to_new[cur].next = old_to_new[cur.next]
        if cur.random:
            old_to_new[cur].random = old_to_new[cur.random]
        cur = cur.next

    return old_to_new[head]

# Test cases
head1 = build_list([(7, None), (13, 0), (11, 4), (10, 2), (1, 0)])
print("Original: ", end=""); print_list(head1)
copy1 = copyRandomList(head1)
print("Copy:     ", end=""); print_list(copy1)
print("Are they different objects?", head1 is not copy1)  # True

head2 = build_list([(1, 1), (2, 1)])
copy2 = copyRandomList(head2)
print("Copy:     ", end=""); print_list(copy2)

head3 = build_list([])
copy3 = copyRandomList(head3)
print("Empty copy:", copy3)  # None

Complexity

• Time: O(n) — two linear passes
• Space: O(n) — hash map stores one entry per node

2. O(1) Space — Interleaving Trick

Intuition

This is a clever technique to avoid the hash map entirely. Instead of a separate map, we interleave copy nodes directly into the original list. Each copy node is inserted right after its original. This lets us find copy_of[node] as node.next — no dictionary needed.

Three phases:

1. Interleave: For each original node, insert copy right after it: A -> A' -> B -> B' -> C -> C'
2. Wire random: node.next.random = node.random.next (copy’s random = copy of original’s random)
3. Separate: Unweave the two lists back apart.

Algorithm

1. Walk the list and insert a copy of each node right after it.
2. Walk again: for each original node cur, if cur.random exists, set cur.next.random = cur.random.next.
3. Walk a third time and separate the interleaved list into original and copy lists.

Solution

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

def build_list(pairs):
    if not pairs:
        return None
    nodes = [Node(val) for val, _ in pairs]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    for i, (_, rand_idx) in enumerate(pairs):
        if rand_idx is not None:
            nodes[i].random = nodes[rand_idx]
    return nodes[0]

def print_list(head):
    node_index = {}
    cur = head
    idx = 0
    while cur:
        node_index[cur] = idx
        cur = cur.next
        idx += 1
    cur = head
    result = []
    while cur:
        rand_idx = node_index[cur.random] if cur.random else None
        result.append(f"[{cur.val}, {rand_idx}]")
        cur = cur.next
    print(" -> ".join(result) if result else "None")

def copyRandomList_o1(head):
    if not head:
        return None

    # Phase 1: interleave copies into original list
    # A -> B -> C  becomes  A -> A' -> B -> B' -> C -> C'
    cur = head
    while cur:
        copy = Node(cur.val)
        copy.next = cur.next
        cur.next = copy
        cur = copy.next  # move to next original node

    # Phase 2: wire random pointers for copies
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next  # copy's random = copy of original's random
        cur = cur.next.next  # skip to next original

    # Phase 3: separate the two lists
    copy_head = head.next
    cur = head
    while cur:
        copy = cur.next
        cur.next = copy.next          # restore original list
        copy.next = copy.next.next if copy.next else None  # build copy list
        cur = cur.next

    return copy_head

# Test cases
head1 = build_list([(7, None), (13, 0), (11, 4), (10, 2), (1, 0)])
copy1 = copyRandomList_o1(head1)
print("O(1) Copy: ", end=""); print_list(copy1)
# Verify original is intact
print("Original:  ", end=""); print_list(head1)

head2 = build_list([(1, 1), (2, 1)])
copy2 = copyRandomList_o1(head2)
print("O(1) Copy: ", end=""); print_list(copy2)

Complexity

• Time: O(n) — three linear passes
• Space: O(1) — no extra data structures (beyond the copy nodes themselves)

Common Pitfalls

Pointing random to original nodes instead of copies. The whole point is a deep copy — every pointer in the new list must point to new nodes. Double-check that you’re using old_to_new[node.random] not node.random itself.

Using .get() vs direct key access. When a node’s .next or .random is None, old_to_new[None] will raise a KeyError. Use old_to_new.get(node.next) which safely returns None, or add an explicit if check.

Forgetting to restore the original list in the O(1) approach. The interleaving technique modifies the original list temporarily. The separation step must cleanly restore cur.next = copy.next for all original nodes.