Copy List with Random Pointer

Problem

You are given a linked list where each node has a next pointer and a random pointer. The random pointer may point to any node in the list, or to None.

Return a deep copy of the list. The copy must contain the same number of new nodes with the same values, and its next and random pointers must reproduce the structure of the original list. No pointer in the copy may reference a node in the original list, and no pointer in the original may reference a node in the copy.

Examples

Notation: [val, random_index] where random_index is the position of the node the random pointer targets (or null).

Input: [[7,null],[13,0],[11,4],[10,2],[1,0]] → Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] The copy is five new nodes with the same structure; the copy of 13 has its random pointing at the copy of 7.
Input: [[1,1],[2,1]] → Output: [[1,1],[2,1]] Both random pointers point at the second node, including the second node pointing at itself.
Input: [[3,null],[3,0],[3,null]] → Output: [[3,null],[3,0],[3,null]] Duplicate values are allowed; node identity, not value, determines the structure to copy.

Constraints

Number of nodes is in [0, 1000].
-10^4 <= Node.val <= 10^4
random is None or points at a node of the same list.

Think about it first

Hint 1

Copying val and next is a single walk down the list. The hard part is random: when you copy a node, the node its random points at may not have been copied yet. How do you translate "original node X" into "copy of X"?

Hint 2

A dictionary mapping original node → its clone answers that translation in O(1). Two passes: first create all clones, then wire every clone's next and random through the map.

Hint 3

To do it with O(1) extra space: splice each clone right after its original (A -> A' -> B -> B' -> ...). Then original.random.next is the clone's random target. A third pass unzips the two lists.

TL;DR

Hash map original→clone (O(n) time, O(n) space), or the interleaving trick for O(n) time, O(1) extra space.

Approach 1 — Brute force: copy nodes, then hunt for each random target

Clone the list following next only. Then for each node, find its random target by walking the original list counting positions, and walk the copy the same number of steps.

# Definition for a Node.
# class Node:
#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
#         self.val = int(x)
#         self.next = next
#         self.random = random

from typing import Optional


def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
    if not head:
        return None
    # clone the spine
    dummy = Node(0)
    tail = dummy
    node = head
    while node:
        tail.next = Node(node.val)
        tail = tail.next
        node = node.next
    # for each node, locate random by index and replay in the copy
    src = head
    dst = dummy.next
    while src:
        if src.random:
            idx = 0
            probe = head
            while probe is not src.random:
                probe = probe.next
                idx += 1
            target = dummy.next
            for _ in range(idx):
                target = target.next
            dst.random = target
        src = src.next
        dst = dst.next
    return dummy.next

Complexity: O(n^2) time (a linear search per node), O(1) extra space.

At n = 1000 this is about a million probe steps. It works, but the repeated search re-derives a node-to-clone correspondence that could be stored once and reused.

Approach 2 — Hash map from original to clone

The insight: the difficulty is translating a pointer to an original node into a pointer to that node’s clone. A dictionary keyed by node identity provides that mapping directly. Pass 1 creates one clone per original; pass 2 wires next and random by lookup, and by then every target’s clone exists.

# Definition for a Node.
# class Node:
#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
#         self.val = int(x)
#         self.next = next
#         self.random = random

from typing import Optional


def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
    clone = {None: None}
    node = head
    while node:
        clone[node] = Node(node.val)
        node = node.next
    node = head
    while node:
        clone[node].next = clone[node.next]
        clone[node].random = clone[node.random]
        node = node.next
    return clone[head]

(Seeding the map with {None: None} lets clone[node.next] and clone[node.random] handle missing targets with no ifs.)

Walkthrough on [[7,null],[13,0],[11,4],[10,2],[1,0]]: pass 1 builds five clones 7',13',11',10',1' and the map {7:7', 13:13', 11:11', 10:10', 1:1', None:None}. Pass 2 at node 13: clone[13].next = clone[11] = 11', clone[13].random = clone[7] = 7'. Every wire in the copy is resolved by one dictionary lookup; the result is the same shape over fresh nodes.

Complexity: O(n) time, O(n) space for the map.

Approach 3 — Interleave, wire, unzip (O(1) extra space)

The insight: instead of a dictionary, encode the original-to-clone mapping in the list itself: splice each clone immediately after its original (A -> A' -> B -> B' -> ...). The clone of any node x is then x.next, so a clone’s random target is original.random.next. Three passes: splice, wire randoms, unzip.

After pass 1 the list is interleaved, so each clone sits directly after the node it copies:

flowchart LR
    A[A] --> Ac[A clone] --> B[B] --> Bc[B clone] --> C[C] --> Cc[C clone]

# Definition for a Node.
# class Node:
#     def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
#         self.val = int(x)
#         self.next = next
#         self.random = random

from typing import Optional


def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
    if not head:
        return None
    # pass 1: splice a clone after every original
    node = head
    while node:
        node.next = Node(node.val, node.next)
        node = node.next.next
    # pass 2: wire the clones' random pointers
    node = head
    while node:
        if node.random:
            node.next.random = node.random.next
        node = node.next.next
    # pass 3: unzip the two lists, restoring the original
    new_head = head.next
    node = head
    while node:
        copy = node.next
        node.next = copy.next
        copy.next = copy.next.next if copy.next else None
        node = node.next
    return new_head

Walkthrough on [[1,1],[2,1]] (nodes A=1, B=2, both randoms → B): pass 1 makes A -> A' -> B -> B'. Pass 2: A.random is B, so A'.random = B.next = B'; B.random is B, so B'.random = B.next = B' — the self-pointing random is reproduced. Pass 3 unzips back to A -> B and A' -> B', and returns A'.

Complexity: O(n) time, O(1) extra space (the clones themselves are the required output, not overhead).

Common pitfalls

Mapping by value instead of node identity — duplicate values collapse into one clone and the structure is wrong. Key the dict on the node object.
Setting random during the same pass that creates clones without a map: the target’s clone may not exist yet. Either two passes or on-demand creation.
In the interleaving version, wiring randoms with node.random.next after starting to unzip — the interleaving is destroyed, so passes 2 and 3 must not be merged.
Forgetting to restore the original list in pass 3 — LeetCode checks that the input list is unmodified.

Pattern takeaway

Deep-copying any structure with arbitrary internal pointers is a two-phase job: first establish a one-to-one old-to-new correspondence, then translate every edge through it. A hash map is the direct way to store that correspondence. The interleaving trick is the space-optimized variant: it stashes the mapping inside the structure itself, which is the technique to reach for whenever O(1) auxiliary space is required.