39.Copy List With Random Pointer

MediumLinked List · 5/11

Problem

A linked list of length n is given where each node has two pointers: next (the usual next node) and random, which can point to any node in the list or null.

Build a deep copy: exactly n brand-new nodes, where each copy has the same val as its original, and the copies' next and random pointers point to the corresponding copied nodes — never to nodes of the original list. Return the head of the copied list.

Examples

Input:  head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Each pair is [val, index of random node]. The copy has the same shape,
but every node is a new object.

Input:  head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Explanation: Both nodes' random pointers point to the second node.

Input:  head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Explanation: Values are not unique, so you cannot match nodes by value.

Constraints

0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or points to some node in the linked list.

💡 Key Insight

The hard part is the random pointer: when you copy a node, the node its random points to may not have been copied yet. The fix is to separate creating nodes from wiring them. A HashMap<original, copy> lets you look up any node's copy in O(1); the optimal trick stores that same mapping inside the list by placing each copy right after its original, so original.random.next is the copy of the random target.

Brute Force (Index Lookup)

TimeO(n²)SpaceO(n)

Intuition

Copy the list following next only, keeping copies in an array. For each original node, find which index its random points to by scanning from the head, then point the copy at the copy with the same index.

Algorithm

Walk the list, creating copies in copies[] and linking copies[i].next = copies[i + 1].
For each original node i with non-null random:
- Scan from head to find the index j of random.
- Set copies[i].random = copies[j].
Return copies[0] (or null).

Visualization

original: 7 -> 13 -> 11 -> 10 -> 1
13.random = 7  -> scan: 7 is index 0 -> copy13.random = copies[0]
11.random = 1  -> scan: 1 is index 4 -> copy11.random = copies[4]

Code

java

import java.util.ArrayList;
import java.util.List;

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        List<Node> copies = new ArrayList<>();
        for (Node curr = head; curr != null; curr = curr.next) {
            copies.add(new Node(curr.val));
        }
        for (int i = 0; i + 1 < copies.size(); i++) {
            copies.get(i).next = copies.get(i + 1);
        }
        int i = 0;
        for (Node curr = head; curr != null; curr = curr.next, i++) {
            if (curr.random == null) continue;
            // Find the index of the random target by scanning from head
            int j = 0;
            Node probe = head;
            while (probe != curr.random) {
                probe = probe.next;
                j++;
            }
            copies.get(i).random = copies.get(j);
        }
        return copies.get(0);
    }
}

Complexity

Time: O(n²) — each random pointer may require scanning the whole list.
Space: O(n) — the array of copies (needed anyway for the output).

Hash Map (Two Passes)

TimeO(n)SpaceO(n)

Intuition

Map every original node to its copy. In the first pass create all copies; in the second pass, every pointer target already has a copy, so copy.next = map.get(orig.next) and copy.random = map.get(orig.random). Mapping null to null handles missing pointers.

Algorithm

Create map with map.put(null, null).
Pass 1: for each node, map.put(node, new Node(node.val)).
Pass 2: for each node, set map.get(node).next = map.get(node.next) and map.get(node).random = map.get(node.random).
Return map.get(head).

Visualization

flowchart LR
    O7["original 7"] --> O13["original 13"] --> O11["original 11"]
    C7["copy 7'"] --> C13["copy 13'"] --> C11["copy 11'"]
    O7 -.->|"map"| C7
    O13 -.->|"map"| C13
    O11 -.->|"map"| C11

When wiring 13': 13.random = 7, so 13'.random = map.get(7) = 7'.

Code

java

import java.util.HashMap;
import java.util.Map;

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> oldToNew = new HashMap<>();
        oldToNew.put(null, null); // so null pointers map to null

        // Pass 1: create every copy
        for (Node curr = head; curr != null; curr = curr.next) {
            oldToNew.put(curr, new Node(curr.val));
        }
        // Pass 2: wire next and random using the map
        for (Node curr = head; curr != null; curr = curr.next) {
            Node copy = oldToNew.get(curr);
            copy.next = oldToNew.get(curr.next);
            copy.random = oldToNew.get(curr.random);
        }
        return oldToNew.get(head);
    }
}

Complexity

Time: O(n) — two linear passes with O(1) map operations.
Space: O(n) — the map holds one entry per node.

Interleaving NodesOptimal

TimeO(n)SpaceO(1) extra

Intuition

Instead of a map, put each copy directly after its original: A → A' → B → B' → …. Now the copy of any node X is just X.next. So A'.random = A.random.next. Finally, unweave the two lists, restoring the original.

Algorithm

Weave: for each original curr, insert copy = new Node(curr.val) between curr and curr.next.
Set randoms: for each original curr (every other node), if curr.random != null, set curr.next.random = curr.random.next.
Unweave: walk again, setting curr.next = copy.next (restore original) and copy.next = copy.next.next (link copies), if present.
Return the copied head (saved as head.next after step 1).

Dry Run

flowchart LR
    A["1<br/>random -> 2"] --> A2["1'"]
    A2 --> B["2<br/>random -> 2"]
    B --> B2["2'"]
    B2 --> N["null"]

For input [[1,1],[2,1]] after weaving: 1.random = 2, so 1'.random = 2.next = 2'; 2.random = 2, so 2'.random = 2.next = 2'. Unweaving gives 1 → 2 and 1' → 2'.

Code

java

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        // 1. Weave copies in: A -> A' -> B -> B' -> ...
        for (Node curr = head; curr != null; curr = curr.next.next) {
            Node copy = new Node(curr.val);
            copy.next = curr.next;
            curr.next = copy;
        }
        // 2. The copy of X is X.next, so copy.random = original.random.next
        for (Node curr = head; curr != null; curr = curr.next.next) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
        }
        // 3. Unweave into two separate lists
        Node copyHead = head.next;
        for (Node curr = head; curr != null; curr = curr.next) {
            Node copy = curr.next;
            curr.next = copy.next;                 // restore original link
            if (copy.next != null) {
                copy.next = copy.next.next;        // link to next copy
            }
        }
        return copyHead;
    }
}

Complexity

Time: O(n) — three linear passes.
Space: O(1) extra — apart from the n output nodes, only a few pointers are used.

Complexity Comparison

Approach	Time	Space (extra)
Index Lookup	O(n²)	O(n)
Hash Map	O(n)	O(n)
Interleaving Nodes	O(n)	O(1)

Common Pitfalls

Setting copy.random = orig.random — that points the copy into the original list, which is not a deep copy.
Trying to wire random in the same pass as creating nodes, before the target's copy exists.
Matching nodes by value — values can repeat, so you must map by node identity.
In the interleaving approach, forgetting to restore the original list's next pointers (LeetCode checks the input is unmodified).
Not checking curr.random != null before calling curr.random.next.