forked from cmhungsteve/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
copy-list-with-random-pointer.cpp
40 lines (36 loc) · 1.14 KB
/
copy-list-with-random-pointer.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Time: O(n)
// Space: O(1)
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
// Insert the copied node after the original one.
for (auto *curr = head; curr; curr = curr->next->next) {
auto *node = new RandomListNode(curr->label);
node->next = curr->next;
curr->next = node;
}
// Update random node.
for (auto *curr = head; curr; curr = curr->next->next) {
if (curr->random) {
curr->next->random = curr->random->next;
}
}
// Seperate the copied nodes from original ones.
RandomListNode dummy(0);
for (auto *curr = head, *copy_curr = &dummy;
curr;
copy_curr = copy_curr->next, curr = curr->next) {
copy_curr->next = curr->next;
curr->next = curr->next->next;
}
return dummy.next;
}
};