Clone Linked List with Random Pointer
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 200 - ◆
-1000 ≤ node value ≤ 1000 - ◆
This platform's judge represents each node's random pointer as an index: randomIndices[i] is the position of the node that node i's random pointer targets, or -1 for none
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Two Passes with a HashMap
GoodFirst pass: create every new node up front, storing each one in a map keyed by its original position — no links are wired yet. Second pass: revisit every original position and set the new node's .next and .random by looking up the target position in that same map. Splitting node creation from link-wiring into two full passes keeps the logic simple, at the cost of walking the list twice.
O(n)O(n)1class Solution {
2 static class RNode {
3 int val;
4 RNode next;
5 RNode random;
6 RNode(int val) { this.val = val; }
7 }
8
9 public int[][] copyRandomList(int[] values, int[] randomIndices) {
10 int n = values.length;
11 Map<Integer, RNode> map = new HashMap<>();
12 for (int i = 0; i < n; i++) {
13 map.put(i, new RNode(values[i]));
14 }
15 for (int i = 0; i < n; i++) {
16 RNode node = map.get(i);
17 if (i + 1 < n) node.next = map.get(i + 1);
18 if (randomIndices[i] != -1) node.random = map.get(randomIndices[i]);
19 }
20 int[][] result = new int[n][2];
21 for (int i = 0; i < n; i++) {
22 RNode node = map.get(i);
23 result[i][0] = node.val;
24 result[i][1] = -1;
25 if (node.random != null) {
26 for (Map.Entry<Integer, RNode> e : map.entrySet()) {
27 if (e.getValue() == node.random) { result[i][1] = e.getKey(); break; }
28 }
29 }
30 }
31 return result;
32 }
33}Optimal — Recursive Clone with Memoization
OptimalClone the list with a single recursive pass instead of two explicit ones. Cloning position i creates that node and registers it in a memo table immediately — before recursing any further — then wires .next and .random by recursively cloning whatever those point at. Registering before recursing is what makes this safe even when random pointers form a cycle back to a node still being built: by the time the recursion reaches it again, it's already in the memo table, so the existing (in-progress) node is reused instead of triggering infinite recursion.
O(n)O(n)1class Solution {
2 static class RNode {
3 int val;
4 RNode next;
5 RNode random;
6 RNode(int val) { this.val = val; }
7 }
8
9 private int[] values;
10 private int[] randomIndices;
11 private Map<Integer, RNode> memo;
12
13 public int[][] copyRandomList(int[] values, int[] randomIndices) {
14 this.values = values;
15 this.randomIndices = randomIndices;
16 this.memo = new HashMap<>();
17 int n = values.length;
18 if (n > 0) clone(0);
19 int[][] result = new int[n][2];
20 for (int i = 0; i < n; i++) {
21 RNode node = memo.get(i);
22 result[i][0] = node.val;
23 result[i][1] = node.random == null ? -1 : indexOf(node.random);
24 }
25 return result;
26 }
27
28 private RNode clone(int i) {
29 if (i == -1) return null;
30 if (memo.containsKey(i)) return memo.get(i);
31 RNode node = new RNode(values[i]);
32 memo.put(i, node);
33 node.next = clone(i + 1 < values.length ? i + 1 : -1);
34 node.random = clone(randomIndices[i]);
35 return node;
36 }
37
38 private int indexOf(RNode target) {
39 for (Map.Entry<Integer, RNode> e : memo.entrySet()) {
40 if (e.getValue() == target) return e.getKey();
41 }
42 return -1;
43 }
44}