LeetCode 138题解 | 随机链表的复制

一、题目链接

138.随机链表的复制

二、题目

三、分析

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。

深拷贝一遍原链表，并连接。确定拷贝结点的random指针就需要原结点找到对应的拷贝结点：map< 原结点，拷贝结点>。

四、代码

/*
// 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*> nodeMap;Node* copyhead = nullptr, *copytail = nullptr;Node* cur = head;while (cur){Node* copy = new Node(cur->val);if (copytail == nullptr){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}nodeMap.insert({ cur, copy });// 或者 nodeMap[cur] = copytail;cur = cur->next;}cur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = nodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};