I am trying to solve the Merge K sorted lists

Idea behind the solution:

1. Loop through the list of linkedlists and add each node to the dictionary with the value as key and node as value.
2. In case of duplicate values of linkedlists, add the node as next to the already available key in the dictionary
3. 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}}

CodePudding user response：

Your solution ended up in an infinite loop because of this dummy = all[i].next. It will never become None and the loop will never end.

You can use below code for creating a linked list from the dict

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

sol = sol.next