方法一：哈希表
python
"""
# 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]':
dic = {}
if not head: return None
cur = head
while cur:
dic[cur] = Node(cur.val)
cur = cur.next
cur = head
while cur:
dic[cur].next = dic.get(cur.next)
dic[cur].random = dic.get(cur.random)
cur = cur.next
return dic[head]利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。
算法流程： 若头节点 head 为空节点，直接返回 null 。 初始化： 哈希表 dic ， 节点 cur 指向头节点。 复制链表： 建立新节点，并向 dic 添加键值对 (原 cur 节点, 新 cur 节点） 。 cur 遍历至原链表下一节点。 构建新链表的引用指向： 构建新节点的 next 和 random 引用指向。 cur 遍历至原链表下一节点。 返回值： 新链表的头节点 dic[cur] 。
作者：Krahets 链接：https://leetcode.cn/problems/copy-list-with-random-pointer/solutions/2361362/138-fu-zhi-dai-sui-ji-zhi-zhen-de-lian-b-6jeo/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法二：拼接 + 拆分
空间复杂度O(1)
还没理解