merge k sorted linked lists and return it as one sorted list analyze and describe its complexity definition for singlylinked list listnode class def initself val self val val self next none def mergeklistslists merge list dummy listnodenone curr dummy q priorityqueue for node in lists if node q putnode val node while not q empty curr next q get1 these two lines seem to curr curr next be equivalent to curr q get1 if curr next q putcurr next val curr next return dummy next definition for singly linked list listnode class merge lists only change heap size when necessary merge list these two lines seem to be equivalent to curr q get 1 i think my code s complexity is also o nlogk and not using heap or priority queue n means the total elements and k means the size of list the mergetwolists function in my code comes from the problem merge two sorted lists whose complexity obviously is o n n is the sum of length of l1 and l2 to put it simpler assume the k is 2 x so the progress of combination is like a full binary tree from bottom to top so on every level of tree the combination complexity is n because every level have all n numbers without repetition the level of tree is x ie log k so the complexity is o n log k for example 8 listnode and the length of every listnode is x1 x2 x3 x4 x5 x6 x7 x8 total is n on level 3 x1 x2 x3 x4 x5 x6 x7 x8 sum n on level 2 x1 x2 x3 x4 x5 x6 x7 x8 sum n on level 1 x1 x2 x3 x4 x5 x6 x7 x8 sum n
from heapq import heappop, heapreplace, heapify
from queue import PriorityQueue



class ListNode(object):
    

    def __init__(self, val):
        self.val = val
        self.next = None


def merge_k_lists(lists):
    
    dummy = node = ListNode(0)
    list_h = [(n.val, n) for n in lists if n]
    heapify(list_h)
    while list_h:
        _, n_val = list_h[0]
        if n_val.next is None:
            heappop(list_h)  
        else:
            heapreplace(list_h, (n_val.next.val, n_val.next))
        node.next = n_val
        node = node.next

    return dummy.next


def merge_k_lists(lists):
    
    dummy = ListNode(None)
    curr = dummy
    q = PriorityQueue()
    for node in lists:
        if node:
            q.put((node.val, node))
    while not q.empty():
        curr.next = q.get()[1]  
        curr = curr.next  
        if curr.next:
            q.put((curr.next.val, curr.next))
    return dummy.next