Hot-138 随即链表的复制

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 headNone: 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拼接链表-利用相邻关系-拆分链表-On时间O1空间 # 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