我正在嘗試解決 Merge K 排序串列
Idea behind the solution:
- Loop through the list of linkedlists and add each node to the dictionary with the value as key and node as value.
- In case of duplicate values of linkedlists, add the node as next to the already available key in the dictionary
- Sort the keys and loop through the dictiory to merge all the linkedlists Problem I am facing:
I am not able to merge back all the linked lists, following is the code:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
all={}
if not lists or len(lists)==0:
return None
for node in lists:
while(node!=None):
temp1=ListNode()
temp1.val=node.val
temp1.next = None
if(node.val in all.keys()):
temp = all[temp1.val]
temp.next = temp1
all[node.val]=temp
temp=None
node=node.next
continue
all[node.val]=temp1
node=node.next
s=sorted(all.keys())
disp=[]
sol=ListNode()
dummy = all[s[0]]
# This is where I am really stuck and don't really know what to do
# to merge back all nodes into a single linked list and return the linked list
#I got this solution to merge manually for this particular test case, but I need to put this in a loop to generalize :
sol=ListNode()
dummy=sol
dummy.next = all[s[0]]
dummy = dummy.next.next
dummy.next=all[s[1]]
dummy = dummy.next
dummy.next=all[s[2]]
dummy = dummy.next
dummy.next=all[s[3]]
dummy = dummy.next.next
dummy.next=all[s[4]]
dummy = dummy.next
dummy.next=all[s[5]]
dummy = dummy.next
return sol.next
the dictionary :
all= {1: ListNode{val: 1, next: ListNode{val: 1, next: None}}, 4: ListNode{val: 4, next: ListNode{val: 4, next: None}}, 5: ListNode{val: 5, next: None}, 3: ListNode{val: 3, next: None}, 2: ListNode{val: 2, next: None}, 6: ListNode{val: 6, next: None}}
uj5u.com熱心網友回復：
因此，您的解決方案最終陷入無限回圈dummy = all[i].next。它永遠不會變成None，回圈也永遠不會結束。
您可以使用以下代碼從 dict 創建鏈接串列
dummy = sol = ListNode()
for key in sorted(all):
dummy.next = all[key]
while dummy.next:
dummy = dummy.next
sol = sol.next
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/441201.html
標籤：python python-3.x data-structures linked-list singly-linked-list
上一篇：洗掉重復項，但將值相加為一