题目
138. 随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示： - 0 <= n <= 1000
- -104 <= Node.val <= 104
- Node.random 为 null 或指向链表中的节点。
我的代码（Python）
/*
// 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) {
if (!head) {
return NULL;
}
std::map<Node*, Node*> copiedNodes;
std::map<Node*, std::vector<Node*>> toBeModifiedNodes;
Node* fakeHead = new Node(-1);
Node* ori_tmp = head;
Node* tar_tmp = fakeHead;
while (ori_tmp) {
Node* newNode = new Node(ori_tmp->val);
tar_tmp->next = newNode;
copiedNodes[ori_tmp] = newNode;
std::map<Node*, std::vector<Node*>>::iterator tar_it = toBeModifiedNodes.find(ori_tmp);
if (tar_it != toBeModifiedNodes.end()) {
for(std::vector<Node*>::iterator it = tar_it->second.begin(); it != tar_it->second.end(); it++) {
(*it)->random = newNode;
}
toBeModifiedNodes.erase(tar_it);
}
if (ori_tmp->random) {
std::map<Node*, Node*>::iterator nextCopiedIt = copiedNodes.find(ori_tmp->random);
if (nextCopiedIt != copiedNodes.end()) {
newNode->random = nextCopiedIt->second;
} else {
std::map<Node*, std::vector<Node*>>::iterator nextToBeModified = toBeModifiedNodes.find(ori_tmp->random);
if (nextToBeModified != toBeModifiedNodes.end()) {
nextToBeModified->second.push_back(newNode);
} else {
std::vector<Node*> newVec;
toBeModifiedNodes[ori_tmp->random] = newVec;
toBeModifiedNodes[ori_tmp->random].push_back(newNode);
}
}
}
ori_tmp = ori_tmp->next;
tar_tmp = tar_tmp ->next;
}
Node* result = fakeHead->next;
delete fakeHead;
return result;
}
};点评
最直接的想法，遍历两次：第一次复制链表基础结构并建立新旧结点的映射关系；第二次处理random指针。
官方给出的方法一，是第一次复制时，把random指向的结点递归复制；这样会有一个堆栈问题。
我使用了另外一种方法：复制时判断random是否已经被复制，如果已经复制则直接指向新结点；否则维护一个列表，当random这个结点被复制时把这个列表中的所有结点random指针都做赋值。缓存的规模和官方的方法一差不多。
官方的方法二，在原链表 后面新增复制结点，最后再恢复结构，这个想法非常巧妙。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog