leetcode-链表深度拷贝

点击:题目链接:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

思路

链表拷贝有两种,浅层拷贝和深度拷贝。
浅层拷贝—拷贝后的链表和之前的共享同一内存,即仍指向同一份next链表
深度拷贝—重新申请内存来放置拷贝后的链表

故我们可以直接使用一个map表一一保存每个结点,再进行拷贝复制每个结点的关系。

代码

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

class Node {
public:
int val;
Node* next;
Node* random;

Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};

class Solution {
public:
Node* copyRandomList(Node* head) {
Node* cur = new Node(0);
cur = head;
unordered_map<Node*, Node*> hash;
while(cur != nullptr){ //将每个结点一一对应存入哈希表
hash[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;

while(cur != nullptr){ //拷贝每个节点的对应关系
hash[cur]->next = hash[cur->next];
hash[cur]->random = hash[cur->random];
cur = cur->next;
}
return hash[head];
}
};

小总结

读题的时候一定要确切的明白题意。比如这道,刚读完,我一直以为要自己来决定结点之间的随即关系(浪费了比较长的时间后感觉不对劲)。结果只需要复制原来的。

作者

Dylan Zhu

发布于

2021-03-18

更新于

2021-03-22

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...