【随机链表的复制】python刷题记录

R3-哈希表

参考k神题解 

哈希表法：

"""
# 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]':if not head:return dict={}#复制各节点，并建立“原结点-》新结点”的map映射cur=headwhile cur:dict[cur]=Node(cur.val)cur=cur.nextcur=head#构建新节点的next和random指向while cur:dict[cur].next=dict.get(cur.next)dict[cur].random=dict.get(cur.random)cur=cur.next#返回新链表的头结点return dict[head]

 

ps:

此外，还能使用拼接+拆分法