Algorithm

Copy List with Random Pointer

Linked List Pattern

Copy List with Random Pointer

Each node of a singly linked list has the usual next pointer plus a second random pointer that points to any node in the list or to null. Build a deep copy: a brand-new list of new nodes whose next and random pointers mirror the original's structure exactly, but point only among the new nodes — no new node may reference any original node. Return the head of the copied list. The original list must be left unmodified.

CONSTRAINTS
  • The number of nodes is in the range [0, 1000]
  • -10⁴ <= Node.val <= 10⁴
  • random points to a node in the list, or is null
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]]
Each pair is [value, index-that-random-points-to]. The copy has the same values and the same random targets by position (e.g. node 13's random points to index 0, the node holding 7), but every node and pointer belongs to the new list.
EXAMPLE 2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Both nodes' random pointers target index 1 (the second node). The clone reproduces that: both cloned randoms point to the cloned second node, never to an original.
EXAMPLE 3
Input: head = []
Output: []
An empty list has nothing to copy, so the deep copy is also empty (null).
What is a deep copy here, versus a shallow one?
A deep copy creates entirely new nodes whose next and random pointers reference only the new nodes. A shallow copy would reuse or point back at the original nodes — which is exactly what the problem forbids.
Can a random pointer be null or point to the node itself?
Yes to both. random may be null, and it may point to any node including its own. Mapping null to null and treating self-references like any other target handles these uniformly.
Must the original list be left unchanged?
Yes. The map-based method never touches it; the O(1)-space interleave method temporarily mutates it, so its final pass must fully restore the original next pointers before returning.
Do multiple nodes with the same value cause ambiguity?
No — pointers reference specific node objects, not values, so identical values never confuse which node a random points to.

Cloning a linked list where nodes have "random" pointers is a dependency puzzle. In a standard list, you only need to know the next node to build the copy. But with random pointers, a node might point to someone much further down the line who hasn't been created yet. You can't set a random pointer to a clone until that clone actually exists in memory.

A common way to solve this is using a Hash Map to store the mapping between every original node and its new copy. This allows you to look up any "clone" in O(1) time, but it costs O(N) extra space.

python
# Hash Map Approach (O(N) Space)
mapping = {None: None}
curr = head

# 1. Create all clones and store in map
while curr:
    mapping[curr] = Node(curr.val)
    curr = curr.next

# 2. Connect next and random links
curr = head
while curr:
    mapping[curr].next = mapping[curr.next]
    mapping[curr].random = mapping[curr.random]
    curr = curr.next
return mapping[head]

To achieve O(1) space, we can use the original list itself as the "address book" by performing a technique called DNA Interleaving.

The strategy works in three distinct phases:
- Interweave: For every node X, we create its clone X' and insert it immediately after X. This creates a temporary "DNA chain" like X -> X' -> Y -> Y'.
- Mirror Randoms: Because every clone X' is sitting right next to its parent X, we can find the correct random target easily: X'.random must be X.random.next.
- Extract: We carefully snip the links to separate the original list from the clone list, restoring the original next pointers while stitching the clones together into a fresh deep copy.

python
# 1. Interweave (DNA splicing)
curr = head
while curr:
    new_node = Node(curr.val, curr.next)
    curr.next = new_node
    curr = new_node.next

# 2. Mirror Random Pointers
curr = head
while curr:
    if curr.random:
        curr.next.random = curr.random.next
    curr = curr.next.next

# 3. Extract Clone and Restore Original
dummy = Node(0)
copy_tail = dummy
curr = head
while curr:
    # Stitch the copy together
    copy_tail.next = curr.next
    copy_tail = copy_tail.next
    # Restore the original next link
    curr.next = curr.next.next 
    curr = curr.next
return dummy.next
Worked Example:[[7,null], [13,7]]

Phase 1: Interweaving (DNA Splicing)

7 (r: ∅)
→
13 (r: 7)
→
NULL
We start with the original list containing nodes 7 and 13. Node 7's random (r) points to null (∅); node 13's random points to node 7.
7 (r: ∅)
curr
→
7' (r: ?)
→
13 (r: 7)
→
NULL
We create a clone of node 7 (named 7') with an uninitialized random pointer (?) and insert it immediately after node 7.
7 (r: ∅)
→
7' (r: ?)
→
13 (r: 7)
curr
→
13' (r: ?)
→
NULL
We advance curr to node 13, create its clone 13' (r: ?), and insert it immediately after node 13, yielding the interleaved chain.

Phase 2: Mirroring Random Pointers

7 (r: ∅)
curr
→
7' (r: ∅)
→
13 (r: 7)
→
13' (r: ?)
→
NULL
We return to the head. Since node 7's random is null, we mirror this by setting 7''s random pointer (r) to null (∅).
7 (r: ∅)
→
7' (r: ∅)
→
13 (r: 7)
curr
→
13' (r: 7')
→
NULL
We advance curr to node 13. Since node 13's random is 7, we set its clone 13''s random to 7's clone (13.random.next = 7'), changing '?' to '7''.

Phase 3: Extracting Clone and Restoring Original

7 (r: ∅)
→
7' (r: ∅)
→
13 (r: 7)
→
13' (r: 7')
→
NULL
We extract the first clone: we point dummy.next to 7', and restore node 7's next to point back to node 13.
7' (r: ∅)
→
13' (r: 7')
→
NULL
We extract the second clone: we point 7''s next to 13', and restore node 13's next to null. We return dummy.next, leaving our completed clone list [7', 13'].
Interactive Strategy Visualization
DEEP CLONE ENGINE

3-Pass In-Place Algorithm

7
7'
13
13'
11
11'
INTERLEAVING

Phase Details

Phase 1: Interleaving

Create copy nodes and interleave them with the original: A -> A' -> B -> B' -> C -> C'. Note: Original random pointers exist but are not yet copied.

Memory Insight

Interleaving copy nodes inside the original list eliminates the need for a Hash Map (O(N) space). We trade O(1) space for O(N) time.

Strategy: Constant Space Deep Copy

Time Complexity: O(N) | Space Complexity: O(1) extra space. The most elegant solution for cloning with random pointers.

O(N) Time · O(N) Space Hash Map
→
O(N) Time · O(1) Space Interleave & Detach