#138 Copy List with Random Pointer
frequently reported atMetaAmazonNVIDIAMicrosoftBloombergAdobe
the problem
In plain words
Each node has next and random (pointing to any node or null). Return a deep copy: brand-new nodes whose next and random mirror the original structure.
in head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
out [[7,null],[13,0],[11,4],[10,2],[1,0]]
Each pair is [val, index of random]. The output is a copy built from new nodes.
in head = [[1,1],[2,1]]
out [[1,1],[2,1]]
in head = [[3,null],[3,0],[3,null]]
out [[3,null],[3,0],[3,null]]
- 0 ≤ n ≤ 1000
- -10⁴ ≤ Node.val ≤ 10⁴
- random is null or points to a node in the list
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternHash lookup (seen before?)In-place linked-list rewiring
The hard part is random: it may point to a node you haven't cloned yet. So clone all nodes first, then wire pointers — using a map, or by parking each clone right after its original.
solutions
From brute force to optimal
Pass 1 clones every node into a map. Pass 2 sets clone.next = map.get(orig.next) and clone.random = map.get(orig.random).
- Clone each node into the map.
- Wire next and random through the map.
- Return map.get(head).
Two passes, O(1) average map operations.
The map holds n entries.
class Solution { public Node copyRandomList(Node head) { Map<Node, Node> copyOf = new HashMap<>(); // original → its clone for (Node p = head; p != null; p = p.next) { copyOf.put(p, new Node(p.val)); // pass 1: clone every node } for (Node p = head; p != null; p = p.next) { // pass 2: wire the clones copyOf.get(p).next = copyOf.get(p.next); // get(null) returns null copyOf.get(p).random = copyOf.get(p.random); } return copyOf.get(head); }}Insert each clone right after its original: A → A' → B → B'. Then A'.random = A.random.next. Finally unzip the two lists.
- Weave clones in.
- Set each clone's random from its original's random.next.
- Unzip, restoring the original list.
Three linear passes.
No map — the list itself stores the original → clone link.
class Solution { public Node copyRandomList(Node head) { if (head == null) return null; // 1. weave clones in: 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. a clone's random is the node right after the original's random for (Node p = head; p != null; p = p.next.next) { if (p.random != null) p.next.random = p.random.next; } // 3. unzip into two lists (and restore the original) Node copyHead = head.next; for (Node p = head; p != null; p = p.next) { Node copy = p.next; p.next = copy.next; copy.next = (copy.next != null) ? copy.next.next : null; } return copyHead; }}in the room
How to say it in the interview
talk track
- Start with the map version — clean and obviously correct.
- If asked for O(1) space, describe the weave/unzip idea and stress that the original list is restored.
traps
- Copying
randomas the original's node (shallow copy). - Forgetting to restore the input list in the interleave approach.
what they ask next
Follow-ups
Clone a whole graph (LC 133)?
Same map idea — original → clone — filled during a DFS or BFS, so cycles and shared neighbours are cloned exactly once.
before you submit
Edge cases to test
- Empty list → null.
- A node whose random points to itself.
- Every random is null.
- Duplicate values — identity matters, not values.
practise next
Similar problems
- #133Clone GraphMediumin Graphs
- #1Two SumEasyin Hashing