Typorithm · medium

Copy List with Random Pointer

copy-list-random-pointerlinked-listsclone-mapwire-pointersdeep-copy

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Copy List with Random Pointer

Linked Lists

Two passes: first create every clone in a Map keyed by the original, then wire each clone's next and random via map lookups.

Each node has a random pointer that may target any node, so links cannot be wired in a single forward pass.

First pass: create a clone for every node and store original → clone in a Map.

Second pass: set each clone's next and random by looking up the originals' clones.

Map keyed by the original node.

Pass 1 creates shells, pass 2 wires.

next and random map identically.

function copyRandomList(head) {
  if (head === null) {
    return null;
  }

  const clones = new Map();
  let curr = head;
  while (curr !== null) {
    clones.set(curr, { val: curr.val, next: null, random: null });
    curr = curr.next;
  }

  curr = head;
  while (curr !== null) {
    const clone = clones.get(curr);
    clone.next = curr.next === null ? null : clones.get(curr.next);
    clone.random = curr.random === null ? null : clones.get(curr.random);
    curr = curr.next;
  }

  return clones.get(head);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Original → clone

Map each original node to its fresh copy.

const clones = new Map()

2. Shell copies

The first pass creates every clone with null links.

clones.set(curr, { val: curr.val, next: null, random: null })

3. Wire next

Look up the clone of the original's next node.

clone.next = curr.next === null ? null : clones.get(curr.next)

4. Wire random

The random pointer maps the same way as next.

clone.random = curr.random === null ? null : clones.get(curr.random)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.