Posted on 2023-09-05 13:51
Uriel 閱讀(50)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構 、
閑來無事重切Leet Code
實現鏈表的深度copy，鏈表除了next指針，每個節點還有一個random指針，指向任意節點，copy的時候也要還原
python的dict的妙用
1 #138
2 #Runtime: 28 ms (Beats 92.87%)
3 #Memory: 13.9 MB (Beats 70.54%)
4
5 """
6 # Definition for a Node.
7 class Node:
8 def __init__(self, x, next=None, random=None):
9 self.val = int(x)
10 self.next = next
11 self.random = random
12 """
13
14 class Solution(object):
15 def copyRandomList(self, head):
16 """
17 :type head: Node
18 :rtype: Node
19 """
20 dic = {None:None}
21 cur = head
22 while cur:
23 dic[cur] = Node(cur.val)
24 cur = cur.next
25 cur = head
26 while cur:
27 cp = dic[cur]
28 cp.next = dic[cur.next]
29 cp.random = dic[cur.random]
30 cur = cur.next
31 return dic[head]