Leetcode 138 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。你的任务是 深拷贝 这个链表，并返回新链表的头指针。你的代码 只 接受原链表的头节点 head 作为传入参数。

这个题目的主要难点在于如何处理 random 指针，因为 random 指针可能指向任意节点，所以我们需要一个字典来存储原链表节点和新链表节点的对应关系。通过这个字典，我们可以很容易的找到 random 指针指向的节点。

"""
# 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: 'Optional[Node]') -> 'Optional[Node]':
        if not head: return
        dic = {}
        current = head
        while current:
            dic[current] = Node(current.val)
            current = current.next
        current = head
        while current:
            dic[current].next = dic.get(current.next)
            dic[current].random = dic.get(current.random)
            current = current.next
        return dic[head]