Copy List with Random Pointer

Solving tips

The core difficulty is translating 'pointer to original node X' into 'pointer to clone of X'; a hash map keyed on node identity is that translation.
Two passes: pass 1 creates all clones into the map, pass 2 wires next and random via lookups (by then every target's clone exists); seed the map with {None: None} to avoid null checks.
Key on node IDENTITY, not value: duplicate values must map to distinct clones.
O(n) time, O(n) space for the map; for O(1) extra space, interleave each clone after its original so clone = original.next, wire randoms, then unzip (restore the input).

Problem

You are given a linked list whose nodes carry an extra pointer: besides next, each node has a random pointer that may point to any node in the list — or to nothing (None).

Build and return a deep copy of the list: exactly as many brand-new nodes, with the same values, whose next and random pointers reproduce the original’s shape entirely within the new nodes. No pointer in the copy may reference an original node, and vice versa.

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]] A structurally identical list of five fresh nodes; e.g. the copy of 13 has its random aimed at the copy of 7.
Input: [[1,1],[2,1]] → Output: [[1,1],[2,1]] Both randoms 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 fine; identity, not value, is what must be mirrored.

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 plain walk. The hard part: 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


class Solution:
    def copyRandomList(self, 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 hunt per node), O(1) extra space.

At n = 1000 that’s about a million probe steps — passable, but the quadratic hunt is pure waste: we keep re-deriving a correspondence we could just store.

Approach 2 — Hash map from original to clone

The insight: the whole difficulty is translating “pointer to original node X” into “pointer to clone of X”. A dictionary keyed by node identity is that translation. Pass 1 creates a clone per original; pass 2 wires next and random by lookup — 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


class Solution:
    def copyRandomList(self, 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→clone mapping in the list itself: splice each clone immediately after its original (A -> A' -> B -> B' -> ...). Now the clone of any node x is simply x.next, so a clone’s random target is original.random.next. Three passes: splice, wire randoms, unzip.

# 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


class Solution:
    def copyRandomList(self, 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→new correspondence, then translate every edge through it. A hash map is the direct way to store that correspondence; the interleaving trick shows the space-optimized variant — stashing the mapping inside the structure itself — a move worth remembering whenever O(1) auxiliary space is demanded.