Copy Linked List with Random Pointer

A regular linked list has nodes with next pointers. Copying one is straightforward — walk through the original, creating new nodes and linking them. But add a random pointer to each node — a pointer that can reference any node in the list (or null) — and the problem becomes significantly harder.

The challenge: when you create a copy of node A and its random pointer points to node C, you need node C’s copy, not node C itself. But you might not have created node C’s copy yet. This ordering problem is what makes the question interesting.

Problem statement

Given a linked list where each node has a next pointer and a random pointer, create a deep copy of the list. The deep copy should consist of entirely new nodes, with next and random pointers referencing the new nodes (not the original ones).

LeetCode 138 — Copy List with Random Pointer

Node definition

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

Visual example

Original list:

  Node A (val=7)  ->  Node B (val=13)  ->  Node C (val=11)  ->  Node D (val=10)  ->  Node E (val=1)
  random: None        random: A              random: E            random: C             random: A

Deep copy must create:

  Node A' (val=7)  ->  Node B' (val=13)  ->  Node C' (val=11)  ->  Node D' (val=10)  ->  Node E' (val=1)
  random: None         random: A'             random: E'            random: C'             random: A'

Key: A'.random != A.random. Each copy's random points to the COPY of the original target.

Why naive copying fails

# This does NOT work
def bad_copy(head):
    if not head:
        return None
    new_head = Node(head.val)
    old_cur = head.next
    new_cur = new_head
    while old_cur:
        new_cur.next = Node(old_cur.val)
        new_cur = new_cur.next
        old_cur = old_cur.next

    # Now try to set random pointers...
    # But how do we find the COPY of old_node.random?
    # We have no mapping from original nodes to their copies!

The fundamental issue: given an original node, we need a way to find its corresponding copy. The two approaches below solve this differently.

---

Approach 1: HashMap (O(n) space)

Intuition

Create a hash map that maps each original node to its copy. First pass: create all copies and populate the map. Second pass: use the map to set next and random pointers on the copies.

Algorithm

1. Pass 1: Walk the original list. For each node, create a copy and store the mapping original -> copy in a dictionary.
2. Pass 2: Walk the original list again. For each node, set:
   • copy.next = map[original.next]
   • copy.random = map[original.random]

Implementation

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

    # Pass 1: Create all copy nodes and build the mapping
    old_to_new = {}
    current = head
    while current:
        old_to_new[current] = Node(current.val)
        current = current.next

    # Pass 2: Set next and random pointers using the mapping
    current = head
    while current:
        copy = old_to_new[current]
        copy.next = old_to_new.get(current.next)
        copy.random = old_to_new.get(current.random)
        current = current.next

    return old_to_new[head]

Detailed walkthrough

Original: A(7) -> B(13) -> C(11) -> D(10) -> E(1)
Randoms:  None    A        E        C        A

Pass 1 — Create copies and mapping:
  old_to_new = {
    A: A'(7),
    B: B'(13),
    C: C'(11),
    D: D'(10),
    E: E'(1)
  }

Pass 2 — Wire up pointers:
  For A: A'.next = old_to_new[B] = B'
         A'.random = old_to_new[None] = None
  
  For B: B'.next = old_to_new[C] = C'
         B'.random = old_to_new[A] = A'
  
  For C: C'.next = old_to_new[D] = D'
         C'.random = old_to_new[E] = E'
  
  For D: D'.next = old_to_new[E] = E'
         D'.random = old_to_new[C] = C'
  
  For E: E'.next = old_to_new[None] = None
         E'.random = old_to_new[A] = A'

Result: A'(7) -> B'(13) -> C'(11) -> D'(10) -> E'(1)
        None      A'        E'        C'        A'

Why dict.get() instead of dict[]

We use old_to_new.get(current.next) instead of old_to_new[current.next] because current.next or current.random might be None. The get() method returns None for missing keys, which is exactly what we want for null pointers.

Single-pass variant

You can also do this in a single pass using defaultdict or checking existence:

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

    old_to_new = {}

    def get_or_create(node):
        if node is None:
            return None
        if node not in old_to_new:
            old_to_new[node] = Node(node.val)
        return old_to_new[node]

    current = head
    while current:
        copy = get_or_create(current)
        copy.next = get_or_create(current.next)
        copy.random = get_or_create(current.random)
        current = current.next

    return old_to_new[head]

This creates copies on-demand. When we encounter a node for the first time (via next or random), we create its copy. When we encounter it again, we reuse the existing copy.

Complexity

Metric	Value
Time	O(n) — one or two passes through the list
Space	O(n) — the hash map stores n mappings

---

Approach 2: Interleaving (O(1) space)

Intuition

Instead of using a hash map to find copies, weave the copies directly into the original list. Place each copy immediately after its original. Then the copy of any node is just original.next, giving us O(1) lookup without a hash map.

Algorithm

Three passes:

1. Pass 1 — Interleave: Create a copy of each node and insert it right after the original.
2. Pass 2 — Set random pointers: For each original node, set copy.random = original.random.next (the copy of the random target).
3. Pass 3 — Separate: Extract the copy nodes into their own list, restoring the original list.

Visual walkthrough

Original: A -> B -> C -> D

Pass 1 — Interleave:
  A -> A' -> B -> B' -> C -> C' -> D -> D' -> None
  (A' is a copy of A, B' is a copy of B, etc.)

Pass 2 — Set random pointers:
  If A.random = C, then A'.random = C.next = C'
  The copy of any node X is always X.next in the interleaved list.

Pass 3 — Separate:
  Original: A -> B -> C -> D -> None
  Copy:     A' -> B' -> C' -> D' -> None

Implementation

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

    # Pass 1: Create interleaved copies
    # A -> B -> C  becomes  A -> A' -> B -> B' -> C -> C'
    current = head
    while current:
        copy = Node(current.val)
        copy.next = current.next
        current.next = copy
        current = copy.next  # Move to the next original node

    # Pass 2: Set random pointers for copies
    current = head
    while current:
        copy = current.next
        if current.random:
            copy.random = current.random.next  # .next gives us the copy
        else:
            copy.random = None
        current = copy.next  # Move to the next original node

    # Pass 3: Separate the two lists
    current = head
    new_head = head.next

    while current:
        copy = current.next
        current.next = copy.next  # Restore original's next

        if copy.next:
            copy.next = copy.next.next  # Set copy's next to next copy
        else:
            copy.next = None

        current = current.next  # Move to next original

    return new_head

Detailed walkthrough

Original: A(7) -> B(13) -> C(11)
Randoms:  None    A        B

=== Pass 1: Interleave ===

Step 1: Create A'(7), insert after A
  A(7) -> A'(7) -> B(13) -> C(11)

Step 2: Create B'(13), insert after B
  A(7) -> A'(7) -> B(13) -> B'(13) -> C(11)

Step 3: Create C'(11), insert after C
  A(7) -> A'(7) -> B(13) -> B'(13) -> C(11) -> C'(11)

=== Pass 2: Set random pointers ===

At A: A.random = None, so A'.random = None
At B: B.random = A, so B'.random = A.next = A'
At C: C.random = B, so C'.random = B.next = B'

=== Pass 3: Separate ===

Step 1: current = A
  A.next = A'.next = B  (restore A's original next)
  A'.next = B.next = B' (set A'.next to B')

Step 2: current = B
  B.next = B'.next = C  (restore B's original next)
  B'.next = C.next = C' (set B'.next to C')

Step 3: current = C
  C.next = C'.next = None  (restore C's original next)
  C'.next = None

Original restored: A(7) -> B(13) -> C(11)
Copy created:      A'(7) -> B'(13) -> C'(11)
                   None      A'        B'

Why original.random.next works

In the interleaved list, every original node is followed by its copy. So if original.random points to some node X, then X.next is X’s copy. This gives us the O(1) lookup we need without any hash map.

Interleaved:  A -> A' -> B -> B' -> C -> C'

If A.random = C:
  A'.random should be C' (the copy of C)
  C' is C.next in the interleaved list
  So: A'.random = A.random.next = C.next = C'

Complexity

Metric	Value
Time	O(n) — three passes through the list
Space	O(1) — no extra data structures (copies don’t count as extra space)

---

Comparison

Aspect	HashMap	Interleaving
Time	O(n)	O(n)
Space	O(n)	O(1)
Complexity of code	Simple	More complex
Modifies original list?	No	Temporarily (restored)
Interview recommendation	Start here	Show as optimization

Interview strategy: Present the HashMap approach first — it’s correct, clean, and easy to explain. Then offer the interleaving approach as an optimization when the interviewer asks, “Can you do it with O(1) extra space?”

---

Edge cases

Null random pointers

# Node with random = None
# Both approaches handle this:
# HashMap:       old_to_new.get(None) returns None
# Interleaving:  we check "if current.random" before setting

Self-referencing random pointer

A -> B -> None
A.random = A  (points to itself)
B.random = B

HashMap: A' = old_to_new[A], A'.random = old_to_new[A] = A' (correct)
Interleaving: A'.random = A.random.next = A.next = A' (correct)

Single node

A -> None, A.random = A

HashMap:
  old_to_new = {A: A'}
  A'.next = None
  A'.random = old_to_new[A] = A'

Interleaving:
  After pass 1: A -> A' -> None
  Pass 2: A'.random = A.random.next = A.next = A' (correct)
  Pass 3: A.next = None, A'.next = None

All random pointers are null

Both approaches handle this naturally. The hash map returns None for get(None), and the interleaving approach skips the assignment when current.random is None.

Empty list

# Both approaches start with:
if not head:
    return None

---

Common mistakes

1. Forgetting to handle None random pointers. Always check if current.random before accessing current.random.next in the interleaving approach.

2. Not restoring the original list. In the interleaving approach, Pass 3 must properly restore all next pointers. If you return without separating, the original list is corrupted.

3. Off-by-one in interleaving navigation. In the interleaved list, to move to the next original node, you skip two nodes: current = current.next.next. Getting this wrong causes infinite loops.

4. Using = instead of deep copy for node creation. copy = original creates an alias, not a copy. You must create Node(original.val).

5. Returning head instead of new_head. Both approaches should return the head of the copy list, not the original.

---

Recursive HashMap variant

For completeness, here’s a recursive version that handles the creation lazily:

def copy_random_list_recursive(head: 'Node') -> 'Node':
    visited = {}

    def copy(node):
        if node is None:
            return None

        if node in visited:
            return visited[node]

        # Create the copy (add to visited BEFORE recursing to handle cycles)
        new_node = Node(node.val)
        visited[node] = new_node

        # Recursively copy next and random
        new_node.next = copy(node.next)
        new_node.random = copy(node.random)

        return new_node

    return copy(head)

Important: We add new_node to visited before recursing. This prevents infinite loops when random pointers create cycles (e.g., A.random = B, B.random = A).

Complexity (recursive)

Metric	Value
Time	O(n)
Space	O(n) — hash map + recursion stack

---

Practice problems

Problem	Difficulty	Link
Copy List with Random Pointer	Medium	LeetCode 138
Clone Graph	Medium	LeetCode 133
Clone Binary Tree With Random Pointer	Medium	LeetCode 1485
Clone N-ary Tree	Medium	LeetCode 1490
Linked List Cycle II	Medium	LeetCode 142

Key takeaways

• The HashMap approach is the go-to first solution. It’s clean, correct, and easy to reason about. The key idea: map original nodes to their copies, then wire up pointers using the map.
• The interleaving approach is a space optimization that replaces the hash map with structural embedding — copies live right next to their originals in the list. It’s clever but harder to implement correctly.
• Add to visited before recursing when using a recursive approach with cycles. This prevents infinite recursion.
• This problem is fundamentally about establishing a mapping between original and copy nodes. Every approach achieves this differently, but the core need is the same.
• The interleaving technique appears in other problems too (like O(1) space linked list operations), so it’s worth understanding deeply even if you default to the HashMap approach in interviews.