# 问题 原题链接：[https://leetcode.com/problems/copy-list-with-random-pointer/](https://leetcode.com/problems/copy-list-with-random-pointer/) A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Note: - You must return the copy of the given head as a reference to the cloned list. # 分析过程 - 输入：一个带有随机指针的链表 - 输出：该链表的深拷贝 - 思路：首先遍历链表，拷贝一份。拷贝的同时记录两个字典，1、`旧链表的<节点, 索引>`，2、`新链表的<索引, 节点>`。复制完一遍以后再次遍历，找旧链表中有随机指针的节点。依靠前面第 1 个字典，找出这个节点的索引，然后用这个索引在第 2 个字典里找到在新链表中的节点，赋值即可。 # 解决方法 ```cpp class Solution { public: Node *copyNode(Node *node) { return new Node(node->val, nullptr, nullptr); } Node* copyRandomList(Node* head) { if (!head) { return nullptr; } std::map<Node *, int> oldDict; std::map<int, Node *> newDict; Node *oldTmp = head; Node *newRoot = copyNode(head); Node *newTmp = newRoot; int index = 0; // 第一次遍历，拷贝链表，并且记录字典 while (oldTmp) { // 新链表中的索引到节点 newDict[index] = newTmp; // 旧链表中的节点到索引 oldDict[oldTmp] = index; oldTmp = oldTmp->next; if (oldTmp) { newTmp->next = copyNode(oldTmp); newTmp = newTmp->next; index++; } } // 再次遍历 oldTmp = head; index = 0; while (oldTmp) { Node *ptrNode = oldTmp->random; // 找到有随机指针的节点，联合两个字典找到目标节点 if (ptrNode) { int ptrIndex = oldDict[ptrNode]; newDict[index]->random = newDict[ptrIndex]; } oldTmp = oldTmp->next; index++; } return newRoot; } }; ```