This problem looks busy at first, but the accepted solution is built around one steady invariant. For 138. Copy List with Random Pointer, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
The notes already sitting in the source point us in the right direction:
- WA
- this algo points to random node with right value but wrong index
- 11 / 19 test cases passed.
- [[3,null],[3,0],[3,null]]
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//WA
02//this algo points to random node with right value but wrong index
03//11 / 19 test cases passed.
04//[[3,null],[3,0],[3,null]]
05/*
06// Definition for a Node.
07class Node {
08public:
09 int val;
10 Node* next;
11 Node* random;
12
13 Node(int _val) {
14 val = _val;
15 next = NULL;
16 random = NULL;
17 }
18};
19*/
20
21class Solution {
22public:
23 Node* copyRandomList(Node* head) {
24 if(!head) return nullptr;
25
26 Node* dummy = new Node(-1);
27 Node* newprev = dummy;
28 unordered_map<int, Node*> val2newnodes;
29
30 Node* cur = head;
31
32 while(cur){
33 Node* node = new Node(cur->val);
34 val2newnodes[node->val] = node;;
35 newprev->next = node;
36 newprev = newprev->next;
37 cur = cur->next;
38 }
39
40 Node* newcur = dummy->next;
41
42 cur = head;
43 newcur = dummy->next;
44 while(cur){
45 newcur->random = (cur->random) ? val2newnodes[cur->random->val] : nullptr;
46 cur = cur->next;
47 newcur = newcur->next;
48 }
49
50 return dummy->next;
51 }
52};
53
54//using the map old2new
55//Runtime: 16 ms, faster than 58.60% of C++ online submissions for Copy List with Random Pointer.
56//Memory Usage: 11.5 MB, less than 12.63% of C++ online submissions for Copy List with Random Pointer.
57class Solution {
58public:
59 Node* copyRandomList(Node* head) {
60 if(!head) return nullptr;
61
62 Node* dummy = new Node(-1);
63 Node* newprev = dummy;
64 unordered_map<Node*, Node*> old2new;
65
66 Node* cur = head;
67
68 while(cur){
69 Node* node = new Node(cur->val);
70 //temporarily point to random nodes in old list
71 //later we will update it
72 node->random = cur->random;
73 old2new[cur] = node;
74 newprev->next = node;
75 newprev = newprev->next;
76 cur = cur->next;
77 }
78
79 Node* newcur = dummy->next;
80
81 cur = head;
82 newcur = dummy->next;
83 while(cur){
84 newcur->random = (newcur->random) ? old2new[newcur->random] : nullptr;
85 cur = cur->next;
86 newcur = newcur->next;
87 }
88
89 return dummy->next;
90 }
91};
92
93//build interleaving list to save space
94//Runtime: 12 ms, faster than 91.43% of C++ online submissions for Copy List with Random Pointer.
95//Memory Usage: 11.3 MB, less than 12.63% of C++ online submissions for Copy List with Random Pointer.
96class Solution {
97public:
98 Node* copyRandomList(Node* head) {
99 if(!head) return nullptr;
100
101 Node* cur = head;
102
103 //bulid the interweaving list
104 while(cur){
105 Node* node = new Node(cur->val);
106 node->next = cur->next;
107 cur->next = node;
108 cur = node->next;
109 }
110
111 //assign "random"
112 cur = head;
113 Node* newcur;
114
115 while(cur){
116 newcur = cur->next;
117 newcur->random = cur->random ? cur->random->next : nullptr;
118 cur = cur->next->next;
119 }
120
121 //split the interleaving list to two lists
122 Node* newhead = head->next;
123 newcur = newhead;
124 cur = head;
125 while(newcur){
126 Node* next = cur->next ? cur->next->next : nullptr;
127 Node* newnext = newcur->next ? newcur->next->next : nullptr;
128 cur->next = cur->next ? cur->next->next : nullptr;
129 newcur->next = newcur->next ? newcur->next->next : nullptr;
130 newcur = newnext;
131 cur = next;
132 }
133
134 return newhead;
135 }
136};Cost