Copy List With Random Pointer

1. Problem & Core Objective

Each node has a val, a next, and a random pointer that may point to any node in the list or to null. Produce a deep copy: a brand-new set of nodes with the same structure, where no pointer in the copy refers to a node in the original.

original:  A → B → C
           A.random → C,  B.random → A,  C.random → null

copy:      A' → B' → C'
           A'.random → C',  B'.random → A',  C'.random → null
                    ↑ points at the COPY, not at C

Constraints: 0 <= n <= 1000 · random is null or points to a node in the list

What's actually being tested: handling a forward reference. When you copy node A, its random may point at node C, which you haven't created yet. The whole question is how you resolve "the copy of X" before all copies exist.

2. First-Principles Thought Process

Why one pass can't work

Copy A. Its random points to C. You need C' — but you haven't reached C yet, so C' doesn't exist. You can't write the pointer.

This is a forward reference, and there are only two ways out:

1. Two passes. First create every copy, then wire the pointers when all copies exist.
2. An oracle. Some way to ask "given original node X, what is its copy?"

Both approaches below are really about building that oracle.

The obvious oracle: a hash map

Map<Node, Node> from original to copy. Pass 1 creates every copy and records the mapping. Pass 2 walks again and sets copy.next = map.get(orig.next) and copy.random = map.get(orig.random).

Clean, O(n) time — and O(n) space for the map.

The clever oracle: the list itself

Here's the trick. Insert each copy immediately after its original:

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

Now "the copy of X" is just X.next. The list is the map.

So A'.random = A.random.next: take A's random (which points at some original), then step to its copy. No lookup structure at all.

Finally unweave the two lists and restore the original.

What this really is

The interleaving replaces O(n) auxiliary memory with a structural encoding — the association is stored in the arrangement of the nodes rather than in a side table. That's a recurring trick, and it's the reason this question is Medium rather than Easy.

3. Solution Paths

Approach 1 — Hash map, two passes (brute force, and a perfectly good answer)

public Node copyRandomList(Node head) {
    if (head == null) return null;
    Map<Node, Node> copies = new HashMap<>();

    for (Node p = head; p != null; p = p.next)          // pass 1: create every copy
        copies.put(p, new Node(p.val));

    for (Node p = head; p != null; p = p.next) {        // pass 2: wire them up
        copies.get(p).next   = copies.get(p.next);      // null maps to null
        copies.get(p).random = copies.get(p.random);
    }
    return copies.get(head);
}

• Time O(n) · Space O(n) for the map

Counter-questions on this approach

⭐ "Why does this need two passes?"

The forward reference. When I copy node A, its random might point to a node further down the list whose copy doesn't exist yet. Pass 1 guarantees every copy exists; only then can pass 2 safely resolve every pointer. Trying to do both at once means writing a pointer to something that hasn't been created.

⭐ "copies.get(p.next) when p.next is null — doesn't that break?"

No, and that's why the code has no null checks. HashMap.get(null) returns null rather than throwing, since HashMap permits a null key. So a null next or random maps to null naturally. It's worth knowing this is a HashMap guarantee, not a general one — TreeMap.get(null) throws NullPointerException. See 05.

"Does the map rely on Node implementing equals and hashCode?"

It relies on it not doing so. Node doesn't override either, so it inherits identity semantics from Object — two distinct nodes with the same val are different keys, which is exactly right here since I'm mapping node identity. If Node had a value-based equals, two nodes holding 7 would collide and the copy would be wired wrong.

"Is O(n) space actually a problem?"

Not at n <= 1000 — this passes comfortably and it's clear code. I'd offer it first. But the interleaving version achieves O(1) extra space, and since the interviewer chose a problem whose entire difficulty is the forward reference, the O(1) trick is very likely what they're fishing for.

Approach 2 — Interleave the copies (optimal on space)

public Node copyRandomList(Node head) {
    if (head == null) return null;

    // 1. weave a copy in behind every original:  A → A' → B → B' → ...
    for (Node p = head; p != null; p = p.next.next) {
        Node copy = new Node(p.val);
        copy.next = p.next;
        p.next    = copy;
    }

    // 2. wire the randoms — "the copy of X" is X.next
    for (Node p = head; p != null; p = p.next.next)
        if (p.random != null) p.next.random = p.random.next;

    // 3. unweave, restoring the original list
    Node dummy = new Node(0), copyTail = dummy;
    for (Node p = head; p != null; p = p.next) {
        copyTail.next = p.next;         // take the copy
        copyTail      = copyTail.next;
        p.next        = p.next.next;    // restore the original's next
    }
    return dummy.next;
}

Trace of step 2 — A → B → C with A.random = C:

After weaving, the list is A → A' → B → B' → C → C'.

• p = A. p.random is C. p.random.next is C'. So A'.random = C' ✓

• The lookup is one pointer hop. No map, no search.

• Time O(n) — three passes · Space O(1) beyond the output

Counter-questions on this approach

⭐ "Why can't you wire the randoms during the weaving pass?"

Same forward reference. While weaving, p.random.next may not be a copy yet — if p.random points further down the list, that node hasn't been given its copy. The invariant "X.next is the copy of X" only holds once every node has been interleaved, so the wiring has to be its own pass.

⭐ "Why is step 3 necessary? Can't you just return the copies?"

Because right now the two lists are tangled — the copies' next pointers still point at originals, and the originals' next point at copies. Returning head.next would give you a chain that alternates between copies and originals, which is not a deep copy at all.

Step 3 separates them and, importantly, restores the input. Leaving the caller's list interleaved with foreign nodes would be a serious side effect on a method whose contract is to copy, not mutate.

"In step 3, why does copyTail.next = p.next work without a null check?"

Because in the woven list every original is immediately followed by its copy, so p.next is never null when p is an original. The loop advances p by p.next after restoring, which moves it to the next original. The dummy head means the first copy needs no special handling either.

"Why if (p.random != null) in step 2, but no guard in step 3?"

p.random.next would throw if p.random were null, so that one needs the guard. In step 3 there's nothing nullable being dereferenced — the structure guarantees the pairs. Guards should be present exactly where something can actually be null, not sprinkled defensively.

"Three passes instead of two. Is that worse?"

Still O(n) — three linear passes is 3n, a constant factor. I'm trading a constant factor of time for a factor of n in space, which is the right trade. I'd mention the map version is slightly faster in practice on small inputs because hashing is cheap and the weaving does more pointer writes.

Comparison

4. Why the Optimal Wins

Both are O(n) time, so this is a pure space comparison — and a demonstration of a specific idea.

The map version stores the original→copy association in a side table. The interleaving stores it in the arrangement of the data: put the copy where you can find it, and you don't need to remember where you put it.

That's the whole trick, and it's worth naming because it recurs — marking array elements by negating them, encoding two numbers in one slot, using a node's position as its identity.

The framing worth keeping:

When you need a mapping from old to new, see whether the structure itself can hold it. Placement can replace lookup.

Be honest about the cost: the interleaving mutates the caller's list mid-algorithm and restores it. If the method could throw partway through, it would leave the input corrupted — which is a real argument for the map version in production code.

5. Java Prerequisites

The node

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

HashMap and null keys

map.get(null)     // returns null — no exception
map.put(null, v)  // legal; HashMap allows one null key

TreeMap and Hashtable both throw on a null key. Relying on this is fine, but know it's HashMap-specific.

Identity vs value keys. Node doesn't override equals/hashCode, so HashMap<Node, Node> keys on object identity — which is what this problem needs. If you ever need identity semantics for a class that does override them, use IdentityHashMap.

Advancing two at a time over a woven list

for (Node p = head; p != null; p = p.next.next) { ... }

Safe only while the weave invariant holds — every original is followed by its copy.

6. Interview Communication Guide

Clarifying questions: Can random point to any node, including itself or backwards (yes)? Can it be null (yes)? Must the original list be unchanged afterwards (yes — it's a copy)? Is O(1) extra space required (ask; both answers are defensible)?

The pitch

"The difficulty is a forward reference. When I copy node A, its random might point to node C further down the list — and C' doesn't exist yet, so I can't write that pointer.

So I need two things: every copy to exist before I wire anything, and a way to ask 'what is the copy of X?'.

The direct answer is a HashMap from original to copy. Pass one creates all the copies, pass two wires next and random through the map. O(n) time and O(n) space, and it's clean — HashMap.get(null) returns null, so null pointers need no special handling.

The O(1)-space version replaces the map with the list itself. I weave each copy in directly behind its original, so the list becomes A, A', B, B', C, C'. Now 'the copy of X' is just X.next — the association is stored in the arrangement instead of a side table. So A'.random = A.random.next: follow A's random to an original, then hop to its copy.

Then I unweave, which also restores the caller's list — important, since I mutated it mid-algorithm.

Three linear passes, O(n) time, O(1) extra space."

Edge cases to volunteer:

Name the self-reference case and the duplicate-values case. The first catches solutions that wire to the original by accident; the second catches anyone who tried to key a map on val.

7. Follow-Up Questions — Modified Constraints

⭐ "What if each node had k arbitrary pointers rather than one random?"

The map version is unchanged — loop over the k pointers in pass 2, still O(nk) time and O(n) space. The interleaving version also still works, since X.next remains the oracle regardless of how many pointers need resolving. This is a good question to be asked, because it shows the two approaches scale differently in code complexity but not in principle.

⭐ "Deep-copy an arbitrary graph, not a list."

LeetCode 133. The interleaving trick dies — there's no linear arrangement to weave into. You fall back to the map plus a DFS or BFS: on visiting a node, create its copy if absent, then recurse to its neighbours. The map does double duty as the visited set, which is what stops cycles from looping forever.

"What if the list had a cycle in its next pointers?"

The map version survives if you stop on a node already in the map. The interleaving version breaks outright — p = p.next.next never terminates, and the weave itself corrupts the cycle. Worth stating plainly: the trick assumes a proper, null-terminated list.

"Make it thread-safe / what if another thread reads the list during the copy?"

The interleaving version is unusable — it temporarily corrupts the shared structure, so any concurrent reader sees a list with foreign nodes spliced in. The map version never touches the original, so it's safe under a read lock. This is the strongest practical argument for the map, and worth volunteering.

"Copy only the nodes satisfying some predicate, preserving randoms where both endpoints survive."

Map version, with a filter in pass 1 and a containsKey check in pass 2 — randoms pointing at dropped nodes become null. The interleaving version can't express this, since skipped nodes break the X.next invariant.

"What if n were 10 million?"

The map's overhead becomes real — roughly 48 bytes per HashMap entry on top of the nodes, so ~500 MB just for the table. The interleaving version allocates only the copies themselves. This is the scale where the O(1) trick stops being an interview flourish and starts being the reason the job finishes.