题目
给你一个长度为 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]]
示例 4：
输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。
解题
方法一：直接deepcopy
不过这道题的意思是让我们去定义这个函数，而不是直接调用。
""" # 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: 'Node') -> 'Node': newhead = copy.deepcopy(head) return newhead
补充：python中copy和deepcopy的区别
对于可变变量直接用=,相当于引用
copy（浅拷贝）只对该对象进行拷贝
deepcopy（深拷贝）对该对象和该对象涉及的子对象都进行拷贝
显然这道题，用deepcopy，头节点，就可以将整个链表拷贝下来。
方法二：先找到所有要复制的节点，再连线。
字典中的键为旧的节点，对应的值为新复制的结点。
class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return None lookup = {} node = head # 创建所有节点 while node: lookup[node] = Node(node.val, None, None) node = node.next node = head # 节点连接 while node: lookup[node].next = lookup.get(node.next) lookup[node].random = lookup.get(node.random) node = node.next return lookup[head]
方法三：回溯
回溯算法的第一想法是将链表想象成一张图。链表中每个节点都有 2 个指针（图中的边）。因为随机指针给图结构添加了随机性，所以我们可能会访问相同的节点多次，这样就形成了环。
上图中，我们可以看到随机指针指向了前一个节点，因此成环。我们需要考虑这种环的实现。
此方法中，我们只需要遍历整个图并拷贝它。拷贝的意思是每当遇到一个新的未访问过的节点，你都需要创造一个新的节点。遍历按照深度优先进行。我们需要在回溯的过程中记录已经访问过的节点，否则因为随机指针的存在我们可能会产生死循环。
算法：
从 头 指针开始遍历整个图。
我们将链表看做一张图。下图对应的是上面的有向链表的例子，Head是图的出发节点。
当我们遍历到某个点时，如果我们已经有了当前节点的一个拷贝，我们不需要重复进行拷贝。
如果我们还没拷贝过当前节点，我们创造一个新的节点，并把该节点放到已访问字典中，即：
visited_dictionary[current_node] = cloned_node_for_current_node.
我们针对两种情况进行回溯调用：一个顺着random指针调用，另一个沿着next指针调用。步骤 1 中将 random和 next指针分别红红色和蓝色标注。然后我们分别对两个指针进行函数递归调用：
""" # 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 __init__(self): self.hush = {} def copyRandomList(self, head: 'Node') -> 'Node': if not head: return None if head in self.hush: return self.hush[head] node = Node(head.val,None,None) self.hush[head]=node node.next = self.copyRandomList(head.next) node.random = self.copyRandomList(head.random) return node
