1 题目
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
节点结构为
class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random
2 解析
（1）方法一
第一步： 根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面，比如下图中原节点1不再指向原原节点2，而是指向新节点1
第二步： 是最关键的一步，用来设置新链表的随机指针。
原节点1的随机指针指向原节点3，新节点1的随机指针指向的是原节点3的next
原节点3的随机指针指向原节点2，新节点3的随机指针指向的是原节点2的next
第三步： 新建一条链的头结点，让后将绿色部分的节点取出来赋值到头结点上
（2）方法二
新建一个空字典，key存放原节点，value存放同样的节点，最后返回字典的value即可
注意：
map.get(原节点)，得到的就是对应的新节点
map.get(原节点.next)，得到的就是对应的新节点.next
map.get(原节点.random)，得到的就是对应的新节点.random
3 Python 实现
class Solution: # 方法一：在每个节点后复制一个新节点，再分离出来 ''' def copyRandomList(self, head): if not head: return None # 新建节点 p = head while p: new_node = Node(p.val,None,None) new_node.next = p.next p.next = new_node p = new_node.next # 链接随机节点 p = head while p: if p.random: p.next.random = p.random.next p = p.next.next p = head # 遍历新节点，并赋值到头结点的链接上 dummy = Node(-1,None,None) curr = dummy while p: curr.next = p.next curr = curr.next p = p.next.next return dummy.next ''' # 方法二：构建字典，key存放原始节点，value存放新节点 ''' map.get(原节点)，得到的就是对应的新节点 map.get(原节点.next)，得到的就是对应的新节点.next map.get(原节点.random)，得到的就是对应的新节点.random ''' def copyRandomList(self, head): map_dict = {} p =head while p: new_node = Node(p.val,None,None) map_dict[p] = new_node p = p.next p = head while p: if p.next: map_dict[p].next = map_dict[p.next] if p.random: map_dict[p].random = map_dict[p.random] p = p.next return map_dict[head]
