LeetCode138 复制带随机指针的链表

链接: https://leetcode.cn/problems/copy-list-with-random-pointer/

题意

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
要求深拷贝一个链表,要求链表的random指针也指向正确的结果

解法

做过类似的题目,这边暂时只给出一种简单的解法
使用一个map构建旧节点到新节点的映射
然后两次遍历即可得到复制后的新链表

还有一种解法是将复制后的节点放在原节点之后,然后再将两者分离
这种解法不需要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
/*
// Definition for a Node.
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) {
map<Node*, Node*> mp;
Node* cur = head;
while(cur != nullptr) {
Node* temp = new Node(cur -> val);
mp[cur] = temp;
cur = cur -> next;
}
cur = head;
while(cur != nullptr) {
mp[cur] -> next = mp[cur -> next];
mp[cur] -> random = mp[cur -> random];
cur = cur -> next;
}
return mp[head];
}
};