一、题目
示例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]]
示例4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
提示：
- 0 <= n <= 1000
- -10000 <= Node.val <= 10000
- Node.random 为空（null）或指向链表中的节点。
二、思路
有的同学看到题目的“深拷贝”，大呼很快啊，python中这个深拷贝简单哇，一行代码搞定！二话不说提交：
""" # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': return copy.deepcopy(head)
确实可以通过：
不过面试时面试官肯定不会满意hhh。
从算法角度更好做法是回溯+哈希。使用哈希表unorder_map，存放的key是原链表的节点，对应的value值是key节点的复制节点。利用count查看是否有对应的键key。
利用DFS从head开始遍历整个链表：
（1）每个节点含有随机指针random和常规的next指针，这个随机指针指向的节点是“任意的”，即可能是还未复制出来的节点，那这时候就需要复制操作，这个复制过程即第二点。
（2）利用哈希表的count查看当前node（即key）是否在哈希表中，即查看当前node是否有“复制节点”啦。如果木有则需要new一个节点存放在哈希表中，即存入以node为key的对应的value中，即建立当前结点和“复制结点”的映射。
（3）然后递归调用当前节点node的随机指针random和常规的next指针指向的节点，操作即又进入第二点的过程，进行复制，然后让复制节点的 next 指针和 random 指针指向这两个复制的节点。最后返回已经被访问过的节点的复制节点。
（4）在回溯搜索过程中，如果当前正在搜索的节点出现在了哈希表中，就说明我们已经遍历完了整个链表，此时就可以直接从哈希表中取出复制后的节点的指针并返回。
具体过程如下：
1、从 head 节点开始 dfs 遍历整个图。
2、复制当前节点 node，并使用哈希表hash存贮源节点到复制节点之间的映射。
3、递归调用当前节点 node 的后继节点和随机指针指向的节点，并进行复制，然后让复制节点的 next 指针和 random 指针指向这两个复制的节点。
4、最后返回已经被访问过的节点的复制节点。
时间复杂度分析： O(n)，其中 n 是链表的长度 。
空间复杂度分析： O(n)，其中 n 是链表的长度 。
三、代码
class Solution { public: unordered_map<Node*, Node*> hash; Node* copyRandomList(Node* head) { if (head == NULL) return NULL; return dfs(head); } Node* dfs(Node* node) { if(node == NULL) return NULL; //node节点已经被访问过了,直接从哈希表hash中取出对应的克隆节点返回。 if(hash.count(node)) return hash[node]; Node* clone = new Node(node->val); //复制节点 hash[node] = clone; //建立源节点到复制节点的映射 clone->next = dfs(node->next); //复制边 clone->random = dfs(node->random); return clone; } };
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)