题目

给你一个长度为 n 的链表，每个节点蕴含一个额定减少的随机指针 random ，该指针能够指向链表中的任何节点或空节点。

结构这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针可能示意雷同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

思路

感觉这道题的难点，在于读懂题目说的啥...
其实题目的意思就是：
有一个链表，这个链表的节点，不光有next指针，还有一个random指针，随机指向某个节点或是None。当初让你复制一份这个链表。

def copyRandomList(head):    if not head:        return None        # 设置一个字典    dic = {}    # 头节点处初始化一个指针cur    cur = head    # 第1遍遍历链表的每个节点    while cur!=None:        # 以后节点作为key，以后节点的copy节点作为val，存入字典中        dic[cur] = Node(cur.val)        # 挪动指针，持续下一个节点        cur = cur.next        # 第1遍遍历实现后，每个节点都复制了一份    # cur再放回到表头处    cur = head    # 第2遍遍历，为copy节点进行next和random指针的链接    while cur!=None:        # copy节点的next指向原节点的next的copy        dic[cur].next = dic[cur.next] if cur.next else None        # copy节点的random指向原节点的next的random        dic[cur].random = dic[cur.random] if cur.random else None        # 挪动指针，持续下一个节点        cur = cur.next    # 返回头节点的copy，即复制链表的头节点    return dic[head]