思路

python可以使用调库法，使用深度拷贝

"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':return copy.deepcopy(head)

此外，新的想法就是我们采用字典去存储原节点—>复制后新的节点的映射关系

class Solution:def __init__(self):self.cached_node = {} #这个字典用于存储 原节点 -> 复制后的新节点 的映射关系。def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if head is None:return Noneif head not in self.cached_node:new_node = Node(head.val)self.cached_node[head] = new_nodenew_node.next = self.copyRandomList(head.next)new_node.random = self.copyRandomList(head.random)return self.cached_node[head]