版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 4.0
描述
给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。返回一个深拷贝的链表。
- 浅拷贝(影子克隆):只复制对象的基本类型，对象类型，仍属于原来的引用
- 深拷贝(深度克隆):不仅复制对象的基本类型，同时也复制原对象中的对象，就是说完全是新产生的对象
介绍两种方法，分别需要： O(n) time, O(n) space 和 O(n) time, O(1) space
Solution1
三遍遍历。 O(n) time, O(n) space
分成3步：
- 复制节点，如A-B-C => A-A’-B-B’-C-C’
- 依次遍历节点A,B,C，将A’B’C’这些节点的随机指针与其一致
- 分离成 A-B-C 和 A’-B’-C’，A’-B’-C’便是所求链表
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
|
RandomListNode* copyRandomList_nn(RandomListNode* head)
{
if (head == nullptr) return nullptr;
RandomListNode *cur = head;
while (cur) {
RandomListNode *node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
cur = head;
while (cur) {
RandomListNode *node = cur->next;
if (cur->random == cur) node->random = node;
else if (cur->random) node->random = cur->random->next;
cur = cur->next->next;
}
RandomListNode *copy = cur = head->next;
while (cur->next) {
cur->next = cur->next->next;
cur = cur->next;
}
return copy;
}
|
Solution2
将各节点依次往后移一位，新建最后一位节点。 O(n) time, O(1) space
分成两步：
- 移动：1->2->3->null => 1->1->2->3->null
- 调整指针关系
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
41
42
|
RandomListNode* copyRandomList_n1(RandomListNode* head)
{
if (head == nullptr) return nullptr;
RandomListNode *prev = head, *cur = head->next;
RandomListNode *copy;
int prev_label = head->label, cur_label;
while (cur) {
cur_label = cur->label;
cur->label = prev_label;
prev_label = cur_label;
prev = cur;
cur = cur->next;
}
RandomListNode *last = new RandomListNode(prev_label);
prev->next = last;
prev = head, cur = head->next;
RandomListNode *cur_random = head->random, *prev_random;
while (cur) {
prev_random = cur_random;
cur_random = cur->random;
if (prev_random == prev) cur->random = cur;
else if (prev_random) cur->random = prev_random->next;
else cur->random = nullptr;
prev = cur;
cur = cur->next;
}
return head->next;
}
|
END.
近期评论