A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list.
Return the head of the copied linked list.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Challenge: Can't just copy next pointers - random pointers reference nodes we may not have created yet!
Key Insight: Need to maintain mapping between original nodes and their copies.
Why HashMap Works:
This is a Deep Copy with References problem:
def copyRandomList(self, head):
if not head:
return None
# Map: old node → new node
old_to_new = {}
# First pass: create all nodes
curr = head
while curr:
old_to_new[curr] = Node(curr.val)
curr = curr.next
# Second pass: set next and random
curr = head
while curr:
if curr.next:
old_to_new[curr].next = old_to_new[curr.next]
if curr.random:
old_to_new[curr].random = old_to_new[curr.random]
curr = curr.next
return old_to_new[head]
# Step 1: Create copies and interweave
# Original: A → B → C
# Result: A → A' → B → B' → C → C'
curr = head
while curr:
copy = Node(curr.val)
copy.next = curr.next
curr.next = copy
curr = copy.next
# Step 2: Set random pointers
curr = head
while curr:
if curr.random:
curr.next.random = curr.random.next
curr = curr.next.next
# Step 3: Separate lists
dummy = Node(0)
curr_old = head
curr_new = dummy
while curr_old:
curr_new.next = curr_old.next
curr_old.next = curr_old.next.next
curr_old = curr_old.next
curr_new = curr_new.next
return dummy.next
For list: 7 → 13 → 11, random: [null, 7, 13]
HashMap Approach:
Pass 1: Create nodes and build map
Original: 7 → 13 → 11
Copy: 7' → 13' → 11'
Map: {7→7', 13→13', 11→11'}
Pass 2: Set pointers using map
7'.next = map[7.next] = map[13] = 13'
7'.random = map[7.random] = map[null] = null
13'.random = map[13.random] = map[7] = 7'
11'.random = map[11.random] = map[13] = 13'
Interweaving Approach:
Step 1: Interweave
7 → 7' → 13 → 13' → 11 → 11'
Step 2: Set random
7'.random = 7.random.next = null
13'.random = 13.random.next = 7'
11'.random = 11.random.next = 13'
Step 3: Separate
Original: 7 → 13 → 11
Copy: 7' → 13' → 11'
1/*
2// Definition for a Node.
3class Node {
4 int val;
5 Node next;
6 Node random;
7
8 public Node(int val) {
9 this.val = val;
10 this.next = null;
11 this.random = null;
12 }
13}
14*/
15
16class Solution {
17 public Node copyRandomList(Node head) {
18 if (head == null) {
19 return null;
20 }
21
22 // HashMap: old node → new node
23 Map<Node, Node> oldToNew = new HashMap<>();
24
25 // First pass: create all nodes
26 Node curr = head;
27 while (curr != null) {
28 oldToNew.put(curr, new Node(curr.val));
29 curr = curr.next;
30 }
31
32 // Second pass: set next and random pointers
33 curr = head;
34 while (curr != null) {
35 if (curr.next != null) {
36 oldToNew.get(curr).next = oldToNew.get(curr.next);
37 }
38 if (curr.random != null) {
39 oldToNew.get(curr).random = oldToNew.get(curr.random);
40 }
41 curr = curr.next;
42 }
43
44 return oldToNew.get(head);
45 }
46}
47
48
49// Alternative Solution: Interweaving (O(1) Space)
50class SolutionInterweaving {
51 public Node copyRandomList(Node head) {
52 if (head == null) {
53 return null;
54 }
55
56 // Step 1: Create copies and interweave with originals
57 // A → B → C becomes A → A' → B → B' → C → C'
58 Node curr = head;
59 while (curr != null) {
60 Node copy = new Node(curr.val);
61 copy.next = curr.next;
62 curr.next = copy;
63 curr = copy.next;
64 }
65
66 // Step 2: Set random pointers for copies
67 curr = head;
68 while (curr != null) {
69 if (curr.random != null) {
70 curr.next.random = curr.random.next;
71 }
72 curr = curr.next.next;
73 }
74
75 // Step 3: Separate the two lists
76 Node dummy = new Node(0);
77 Node currOld = head;
78 Node currNew = dummy;
79
80 while (currOld != null) {
81 // Extract copy
82 currNew.next = currOld.next;
83
84 // Restore original list
85 currOld.next = currOld.next.next;
86
87 // Move pointers
88 currOld = currOld.next;
89 currNew = currNew.next;
90 }
91
92 return dummy.next;
93 }
94}
95
96
97// Alternative Solution: Recursive with HashMap
98class SolutionRecursive {
99 private Map<Node, Node> visited = new HashMap<>();
100
101 public Node copyRandomList(Node head) {
102 if (head == null) {
103 return null;
104 }
105
106 return getClonedNode(head);
107 }
108
109 private Node getClonedNode(Node node) {
110 if (node == null) {
111 return null;
112 }
113
114 if (visited.containsKey(node)) {
115 return visited.get(node);
116 }
117
118 // Create new node
119 Node newNode = new Node(node.val);
120 visited.put(node, newNode);
121
122 // Recursively clone next and random
123 newNode.next = getClonedNode(node.next);
124 newNode.random = getClonedNode(node.random);
125
126 return newNode;
127 }
128}
129