AlgoMaster Logo

Copy List with Random Pointer

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

Copying a plain linked list takes one pass: walk the original, create a new node for each value, and link the next pointers as you go. The random pointer breaks that plan. While the copy is being built node by node, a random pointer can reference a node whose copy does not exist yet. Setting copy.random = original.random does not work either, since that points into the original list rather than the copy.

The core challenge is building a mapping from each original node to its copy, so that any random reference in the original list can be translated into the matching reference in the new list.

Key Constraints:

  • 0 <= n <= 1000 → n can be 0, so the code must handle an empty list. Time is not the bottleneck at this size; both approaches below run in O(n), and the real difference between them is space.
  • -10^4 <= Node.val <= 10^4 → Values can be negative and can repeat (Example 3 has three nodes with value 3), so values cannot identify nodes. The mapping must be keyed on node references.
  • Node.random is null or points to some node in the list → Random pointers form arbitrary connections. A random pointer can point forward, backward, to the node itself, or nowhere, so no ordering can be assumed when resolving them.

Approach 1: Hash Map (Two Pass)

Intuition

A hash map solves the mapping problem directly. The first pass creates a copy of every node and records map[original] = copy. The second pass walks the original list again and wires both pointers on each copy, translating original.next and original.random through the map.

Splitting the work into two passes removes the ordering problem: by the time any pointer is wired, every copy already exists, so it does not matter whether a random pointer leads forward or backward.

Algorithm

  1. If head is null, return null.
  2. First pass: iterate through the original list. For each node, create a new node with the same value and record map[original] = copy.
  3. Second pass: iterate through the original list again. For each node, set map[original].next = map[original.next] and map[original].random = map[original.random]. A null next or random translates to null.
  4. Return map[head], the head of the copied list.

Example Walkthrough

1Original list: 7→13→11→10→1, with random pointers 13→7, 11→1, 10→11, 1→7
7
curr
13
11
10
1
null
1/12

Code

The hash map exists only to translate original references into copy references. The next approach stores that mapping in the list structure itself and cuts the extra space to O(1).

Approach 2: Interleaving Nodes (O(1) Space)

Intuition

Instead of using a hash map, we weave the copy nodes directly into the original list. For each original node A, we insert its copy A' right after it, so the list becomes A -> A' -> B -> B' -> C -> C' -> ...

The interleaved structure encodes the mapping: original.next is always that node's copy. For random pointers, if original.random points to some node X, then original.random.next is X's copy, so wiring every random pointer reduces to copy.random = original.random.next.

A final pass splits the interleaved list back into two independent lists and restores the original. The pass order matters: random pointers must be wired before the lists are separated, because original.random.next stops being the copy once the lists are split apart.

Algorithm

  1. If head is null, return null.
  2. Pass 1 (Interleave): For each original node, create a copy and insert it right after the original. A -> B becomes A -> A' -> B -> B'.
  3. Pass 2 (Set random pointers): For each original node whose random is not null, set original.next.random = original.random.next. Advance two nodes at a time to stay on originals.
  4. Pass 3 (Separate lists): Walk the interleaved list, restoring each original's next and linking each copy's next, producing two independent lists.
  5. Return the head of the copy list, the node that sat at head.next while interleaved.

Example Walkthrough

1Original: 7→13→11→10→1, with random pointers 13→7, 11→1, 10→11, 1→7
7
curr
13
11
10
1
null
1/13

Code