23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Notes: 

• Use of PriorityQueue. 
• We need only one current pointer.
• By adding the list index we solve the issue of ListNode not having a less than operator defined. Since tuples are compared element by element, if the tie is broken by list index, the comparator does not even get to comparing the ListNode object. 

def mergeKLists(lists: List[Optional[ListNode]]):

       

    from queue import PriorityQueue

   

    pQ = PriorityQueue()

    for i,head in enumerate(lists):

        if head:

            pQ.put((head.val, i, head))        

                   

    head = ListNode()

    cur = head

   

    while not pQ.empty():

        _,i,smallest = pQ.get()

        cur.next = smallest

        cur = cur.next

        nextOfSmallest = smallest.next

        if nextOfSmallest is not None:

            pQ.put((nextOfSmallest.val, i, nextOfSmallest))

       

    return head.next