我们用哈希表来解决这个问题
首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点
我们将原节点作为key，新节点作为value放入哈希表中
"""
# 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 None
d=dict()
p=head
while p:
new_node=Node(p.val,None,None)
d[p]=new_node
p=p.next
p=head
while p:
if p.next:
d[p].next=d[p.next]
if p.random:
d[p].random=d[p.random]
p=p.next
return d[head]
第一次循环（建映射，创建“影子节点”）
p 是原链表的当前节点（原节点对象）
在字典
d中：key =
p（原节点的引用）value =
Node(p.val, None, None)（一个新建节点对象的引用）
此时新建节点的
next和random都是None，所以这些新节点是“孤立点”
例子：
原链表： A → B → C
哈希表：
d[A] = A'(next=None, random=None)
d[B] = B'(next=None, random=None)
d[C] = C'(next=None, random=None)
第二次循环（接指针，补全结构）
目的：把
d[p]（新节点）内部的next/random指针补好补 next：
原链表：
p.next是原节点的下一个新链表：
d[p].next应该指向d[p.next]（下一个原节点对应的新节点）
补 random：
原链表：
p.random是原节点的随机指向新链表：
d[p].random应该指向d[p.random]（原节点随机指向对应的新节点）
例子（假设 A.random → C）：
第二次循环后：
A'.next = B'
B'.next = C'
A'.random = C'
这样，新链表的节点之间关系和原链表完全一致，但对象是全新的。