1、解法1：直接用dict / map 来做Node到Node的映射：
-O(n)时间，O(n)空间：
""" # 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]': # 解法1：使用O(n)时间和O(n)空间的哈希表法解决： if head==None: return None dic = {} cur = head while cur != None: dic[cur] = Node(cur.val) cur = cur.next # 开始复制 cur = head while cur != None: if cur.next != None: dic[cur].next = dic[cur.next] if cur.random != None: dic[cur].random = dic[cur.random] cur = cur.next return dic[head] # 解法2：使用O(n)时间和O(1)空间的解法2、解法2：拼接链表-利用相邻关系-拆分链表
-O（n）时间，O（1）空间；
""" # 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]': # 解法2：使用O(n)时间和O(1)空间的解法 # 拼接+拆分法：利用相邻关系替代dict/map if not head: return None cur = head # 1、复制各个节点，并且完成拼接： while cur: tmp = Node(cur.val) tmp.next = cur.next cur.next = tmp cur = tmp.next # 2、根据相邻关系，构建random指针 cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 3、拆分链表： cur = head.next res = cur pre = head while cur.next != None: pre.next = pre.next.next cur.next = cur.next.next pre = pre.next cur = cur.next return res
