A music product clones a user’s listening session so a recommendation experiment can shuffle the copy. Each track node has next (the queue) and a jump (random: skip to a saved track, “play this from another slot”). The intern walked next and built a new chain of the same titles. The jumps still pointed at the live session. The experiment’s skip mutated what people were actually hearing.

A deep copy means every next and random lands on a copy, never on an original.

This is an interview writeup, not a hashing lecture. The linked list post owns splice and why get(i) walks. The hash table post owns buckets and collisions. Here we only care about mapping original node objects to their copies so both pointers are lookups, not a restart from head.

The problem

Given the head of a singly linked list, return the head of a deep copy. Each node has a value, a next pointer, and a random pointer that is either null or another node in the same list. The copy uses brand-new nodes. Every next and random on the copy refers to a copied node (or null), never to a node from the input. An empty list copies as null. Values may repeat; identity is the node object, not val.

7 → 13 → 11 → 10 → 1 → null
random: 7→null, 13→7, 11→1, 10→11, 1→7
copy: same vals and jump shape; every pointer on the copy refers to a new node

empty                              →  null
7 → null, 7.random = 7             →  a new node 7 whose random is that copy, not the original

This problem’s node is not the two-field ListNode from Reverse Linked List. It is Node with three fields:

final class Node {
    int val;
    Node next;
    Node random;

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

Note: Copying val along next and leaving random on the originals passes a value-order test and fails any check that identity matters. copy.random = orig.random is a shallow jump. The experiment is still holding production nodes.

Nested search for each random is the honest brute force

First walk copies the next chain — new nodes, random still null. Second walk, for each original, walks again from head until it finds orig.random, keeping a parallel walker on the copy chain, then points the copy’s random there.

Node copyRandomListNested(Node head) {
    if (head == null) {
        return null;
    }
    Node copyHead = new Node(head.val);
    Node orig = head.next;
    Node copy = copyHead;
    while (orig != null) {
        copy.next = new Node(orig.val);
        copy = copy.next;
        orig = orig.next;
    }
    orig = head;
    copy = copyHead;
    while (orig != null) {
        if (orig.random != null) {
            Node walkOrig = head;
            Node walkCopy = copyHead;
            while (walkOrig != orig.random) {
                walkOrig = walkOrig.next;
                walkCopy = walkCopy.next;
            }
            copy.random = walkCopy;
        }
        orig = orig.next;
        copy = copy.next;
    }
    return copyHead;
}

Correct. Quadratic: each of n nodes may walk the whole list to place one jump. At n = 20 this is a rounding error. At a session of thousands of hops you paid a nested search for a question a map answers in expected constant time per pointer: which copy did I already make for this original node?

The map’s keys are original Node objects, not val. Duplicate titles stay different keys.

Pass 1 — create every copy, store original → copy. Do not wire next or random yet; a jump may point forward, and that copy does not exist if you try to wire while you are still allocating.

Pass 2 — walk the originals again. For each current, the copy is copies.get(current). Set copy.next and copy.random through the same map. HashMap.get on a missing key, including null, returns null, so a missing next or random wires to null without a branch.

orig:  A(7) → B(13) → C(11) → null
random: A→null, B→A, C→B

pass 1: map {A:A', B:B', C:C'}     copies exist; next/random still null
pass 2: A'.next=B'   A'.random=null
        B'.next=C'   B'.random=A'
        C'.next=null C'.random=B'
return A'

You never restart a scan from head to place a jump. You never point a copy at an original.

Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    Map<Node, Node> copies = new HashMap<>();
    for (Node current = head; current != null; current = current.next) {
        copies.put(current, new Node(current.val));
    }
    for (Node current = head; current != null; current = current.next) {
        Node copy = copies.get(current);
        copy.next = copies.get(current.next);
        copy.random = copies.get(current.random);
    }
    return copies.get(head);
}

Time is expected O(n) — two walks, one expected-O(1) put or get per node. Space is O(n) for the map, plus the n new nodes the prompt required. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: A map keyed by val is the wrong dictionary. Two nodes with title 7 collapse to one copy. Self-jumps (random points at this) work because copies.get(current) and copies.get(current.random) are the same new node.

What interviewers usually poke next

  • O(1) extra besides the copies (the weave). Interleave each copy beside its original, wire random via A.random.next, then split and restore the input. Three walks, no map. Name the restore out loud; the map is still the interview default.
  • One-pass create-as-you-go. Same map; allocate on first sight of next or random. Correct, messier at the board. Say why two passes are easier to narrate.
  • Empty list / single node / random null / self jump / jump forward or back. All ordinary if the map is identity. Empty returns null; a self jump copies to the new node, not the old one.
  • Clone a graph. Branching adjacency is the same old→new map with a visited walk. This list has one next plus one random; do not reach for DFS coloring unless they change the shape.

You are done with this problem when you can say, out loud, why copying the next chain is not a deep copy, why a nested walk for each random is correct and quadratic, and why the map’s keys are original nodes, not values.