一、題目鏈接

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;}
};