126. Copy List with Random Pointer

The hard part of copying is the random pointer: when you create a clone, the node its random should point to may not exist yet. The trick is to weave each clone right after its original (A → A' → B → B' → …). Now a clone is always reachable as original.next, so 'the clone of X' is simply 'X.next' — which lets us set every random pointer in one pass without a hash map.

Why random pointers are tricky

Copying next is easy — walk the list and chain new nodes. random is the problem: cur.random might point forward to a node whose clone doesn't exist yet, or backward to one already made. A hash map from original→clone solves it in O(n) space. The interleaving trick achieves the same in O(1) extra space by encoding that mapping into the list structure itself.

The three passes

Pass 1 — interleave clones. For each original node A, create its clone A' and splice it in right after A:

A → B → C   becomes   A → A' → B → B' → C → C'

Now the clone of any node X is exactly X.next.

Pass 2 — set the clones' random pointers. For each original cur, its clone is cur.next. The node cur.random points to has its clone at cur.random.next. So:

cur.next.random = (cur.random != null) ? cur.random.next : null

No hash map needed — the interleaving is the lookup table.

Pass 3 — unweave. Separate the two interleaved lists, restoring the original's next chain and stitching the clones into their own list:

cur.next = clone.next;   clone.next = clone.next ? clone.next.next : null

Worked example

List [[7,-1],[13,0],[11,4],[10,2],[1,0]] — values 7,13,11,10,1 with randoms pointing to indices -1,0,4,2,0.

1. Interleave: 7 → 7' → 13 → 13' → 11 → 11' → 10 → 10' → 1 → 1'.
2. Randoms: node 13's random is 7 (index 0); its clone 13' gets random 7.next = 7'. Node 11's random is 1 (index 4); 11' gets 1.next = 1'. And so on. Every clone's random is set by hopping one step from the original's random.
3. Unweave: pull the clones out into 7' → 13' → 11' → 10' → 1', leaving the original intact.

Serializing the copy by index reproduces [[7,-1],[13,0],[11,4],[10,2],[1,0]] — an independent list with identical wiring.

Complexity

• Time: O(n) — three linear passes.
• Space: O(1) extra — no hash map; the interleaving stores the correspondence.

import java.util.*;

class Solution {
    static class Node {
        int val;
        Node next, random;
        Node(int val) { this.val = val; }
    }

    public int[][] copyRandomList(int[][] nodes) {
        int n = nodes.length;
        if (n == 0) return new int[0][];

        Node[] orig = new Node[n];
        for (int i = 0; i < n; i++) orig[i] = new Node(nodes[i][0]);
        for (int i = 0; i < n; i++) {
            if (i + 1 < n) orig[i].next = orig[i + 1];
            int r = nodes[i][1];
            orig[i].random = r == -1 ? null : orig[r];
        }

        Node head = orig[0];

        // 1) Interleave clones: A -> A' -> B -> B' -> ...
        for (Node cur = head; cur != null; ) {
            Node clone = new Node(cur.val);
            clone.next = cur.next;
            cur.next = clone;
            cur = clone.next;
        }

        // 2) Wire clone randoms via the interleaving.
        for (Node cur = head; cur != null; cur = cur.next.next) {
            cur.next.random = cur.random == null ? null : cur.random.next;
        }

        // 3) Unweave.
        Node copyHead = head.next;
        for (Node cur = head; cur != null; ) {
            Node clone = cur.next;
            cur.next = clone.next;
            clone.next = clone.next == null ? null : clone.next.next;
            cur = cur.next;
        }

        // Serialize the copy to [[val, random_index], ...].
        List<Node> list = new ArrayList<>();
        for (Node nd = copyHead; nd != null; nd = nd.next) list.add(nd);
        Map<Node, Integer> idx = new HashMap<>();
        for (int i = 0; i < list.size(); i++) idx.put(list.get(i), i);
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            Node nd = list.get(i);
            res[i][0] = nd.val;
            res[i][1] = nd.random == null ? -1 : idx.get(nd.random);
        }
        return res;
    }
}