合并字典中的链表

Question

我正在尝试解决 Merge K 排序列表

解决方案背后的想法：

1. 遍历链表列表并将每个节点添加到字典中，值为键，节点为值。
2. 如果链表有重复值，将节点添加到字典中已有键的旁边
3. 对键进行排序并循环遍历字典以合并所有链表 我面临的问题：

我无法合并回所有链表，代码如下：

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
 
    

词典：

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}}

Answer 1

由于这个 dummy = all[i].next，您的解决方案陷入了无限循环。它永远不会变成 None 并且循环永远不会结束。

您可以使用以下代码从字典创建链表

dummy = sol = ListNode()
for key in sorted(all):
    dummy.next = all[key]
    while dummy.next:
        dummy = dummy.next

sol = sol.next