随机链表的复制

最直观的方法就是两层循环，建立完所有的节点后，第一层循环遍历节点，第二层循环找到random指向的对应节点并链接。

可以使用哈希表来空间换时间，在建立所有的节点的时候存储新旧节点的对应关系，第二次遍历节点时，直接查表链接到对应的random节点。

更优的方法（细胞分裂法），时间为On，空间为O1.

第一步：克隆细胞，紧紧跟随遍历原链表，每走到一个老节点（比如A），就克隆一个它的影子（A'），然后强行把影子塞到老节点的后面。

• 原本是：A -> B -> C

• 裂变后：A -> A' -> B -> B' -> C -> C'（这一步，我们巧妙地把“映射关系”用相对物理位置记录下来了：老节点的下一个，绝对就是它的克隆体）

第二步：精准复制 Random 指针现在链表变长了，我们再次从头遍历（每次跳两步，只看老节点）。 假设老节点A的random指向了老节点C。 那么影子节点A'的random应该指向C的影子节点C'！翻译成代码就是A.next.random = A.random.next(注意判空)

第三步：完美拆解，现在所有的指针都连好了，我们只需要把这个混合链表，拆成一老一新两个独立的链表。 把A -> B -> C还原，把A' -> B' -> C'拎出来返回。

""" # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if not head: return None cur=head while cur: node=Node(cur.val,cur.next) cur.next=node cur=cur.next.next cur=head while cur and cur.next: if cur.random: cur.next.random=cur.random.next else: cur.next.random=None cur=cur.next.next pre=head new_head=head.next cur=new_head while cur: pre.next=pre.next.next if cur.next: cur.next=cur.next.next else: cur.next=None pre=pre.next cur=cur.next return new_head