Copy List With Random Pointer

MEDIUM✓ CHIP-TIMEDLC #138 — FULL STATEMENT ↗

The drill: Deep-copy a linked list where every node has a second pointer that can jump to any other node in the list (or nowhere) — the copy needs its own nodes, wired with the same next and random shape as the original.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A linked list arrives where every node carries two outgoing links: the usual next pointer to the following node, and a second random pointer that can jump to any node in the list, or to nothing at all.

The job is to build a completely independent deep copy of that structure — new nodes throughout, with the copy's next and random links each mirroring the shape of the original, never pointing back into the original list.

A random pointer that was null in the original stays null in the copy, and two nodes whose random pointers targeted the same original node must have copies whose random pointers target the same copied node.

EX 01

head = [[10, null], [20, 0], [30, 4], [40, 2], [50, 0]]

→ [[10, null], [20, 0], [30, 4], [40, 2], [50, 0]]

MIXED FORWARD/BACKWARD RANDOM TARGETS

EX 02

head = []

→ []

EMPTY LIST

EX 03

head = [[5, 0]]

→ [[5, 0]]

SINGLE NODE, RANDOM POINTS TO ITSELF

list holds up to a few thousand nodes
each node's random pointer may target any node in the list or be null
the copy must use entirely new nodes, never reusing originals
random pointer relationships must be mirrored exactly, node for node

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A copy is easy once every original node already has its twin ready to point to. What structure lets you look up 'the copy of this original node' in O(1) while you're still wiring pointers?

HINT 2 THE STRUCTURE

One pass to create every copy and remember original → copy, then a second pass to set each copy's next and random by looking up the originals' targets in that map.

HINT 3 ONE STEP FROM THE ANSWER

You can skip the map entirely: splice each copy directly after its original (A → A′ → B → B′ → …), use that adjacency to wire random in one pass (node.next.random = node.random.next), then unweave the two lists apart.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE INTERWEAVEPATTERN · INTERLEAVE, WIRE, SPLITlist = [1→3rand, 2→null, 3→1rand]

STEP 1

Deep-copy a 3-node list where random pointers can jump anywhere: node1's random targets node3, node2's random is null, node3's random targets node1.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/copy-list-with-random-pointer.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None

        # interleave a copy right after each original: A -> A' -> B -> B' -> ...
        node = head
        while node:
            nxt = node.next
            copy = Node(node.val)
            node.next = copy
            copy.next = nxt
            node = nxt

        # wire the copies' random pointers using the interleaving as the map
        node = head
        while node:
            if node.random:
                node.next.random = node.random.next
            node = node.next.next

        # unweave the two lists, restoring the original as a side effect
        dummy = Node(0)
        copy_prev = dummy
        node = head
        while node:
            copy = node.next
            node.next = copy.next
            copy_prev.next = copy
            copy_prev = copy
            node = node.next

        return dummy.next

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 33 LN

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None

        mapping = {}
        node = head
        while node:
            mapping[node] = Node(node.val)
            node = node.next

        node = head
        while node:
            mapping[node].next = mapping.get(node.next)
            mapping[node].random = mapping.get(node.random)
            node = node.next

        return mapping[head]

TIME O(N)SPACE O(N)PYTHON · TRAINING PACE · 18 LN

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

        for (Node n = head; n != null; ) {
            Node nxt = n.next;
            Node copy = new Node(n.val);
            n.next = copy;
            copy.next = nxt;
            n = nxt;
        }

        for (Node n = head; n != null; n = n.next.next) {
            if (n.random != null) {
                n.next.random = n.random.next;
            }
        }

        Node dummy = new Node(0);
        Node copyPrev = dummy;
        for (Node n = head; n != null; n = n.next) {
            Node copy = n.next;
            n.next = copy.next;
            copyPrev.next = copy;
            copyPrev = copy;
        }
        return dummy.next;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 29 LN

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

        Map<Node, Node> mapping = new HashMap<>();
        for (Node n = head; n != null; n = n.next) {
            mapping.put(n, new Node(n.val));
        }
        for (Node n = head; n != null; n = n.next) {
            mapping.get(n).next = mapping.get(n.next);
            mapping.get(n).random = mapping.get(n.random);
        }
        return mapping.get(head);
    }
}

TIME O(N)SPACE O(N)JAVA · TRAINING PACE · 15 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED