给你一个长度为 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 作为传入参数。
题目很长，简单来说就是，链表的节点有一个next指针和random指针，next指针指向下一个节点，random节点指向其他节点。
首先是先复制一下链表，即每个原节点后面复制一个新节点，先操作next指针。
然后是把复制后的节点，操作一下random指针。
容易发现，新节点的random指向原节点random指向的next节点。
最后就是拆开新链表和原链表，因为题目要求需要保存原链表，所以需要用两个指针。
# Definition for a Node.classNode:def__init__(self,x,next=None,random=None):self.val=int(x)self.next=nextself.random=randomclassSolution(object):defcopyRandomList(self,head):""" :type head: Node :rtype: Node """ifnothead:returnNonep=headwhilep:new_node=Node(p.val)new_node.next=p.nextp.next=new_node p=new_node.nextp=headwhilep:ifp.random:p.next.random=p.random.nextp=p.next.nextdummy=Node(0)copy_cur=dummy# 负责构建复制链表cur=head# 负责遍历原链表whilecur:copy_node=cur.next# 先保存副本（比如 A'）cur.next=copy_node.next# 恢复原链表（A -> B）copy_cur.next=copy_node# 把副本接到复制链表（dummy -> A'）copy_cur=copy_node# 移动复制链表的指针cur=cur.next# 移动原链表的指针到 Breturndummy.next
