23. Merge K Sorted Lists

We want to sort all of the items in the list. To do so, add them to a heap, and then iterate through the K sorted lists. We want to first add the heads of the lists to the heap, and then we pop the minimum value. We then add the next item from that list and continue on.

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        curr = []
 
        head = ListNode()
        res = head
 
        for i, l in enumerate(lists):
            if l is None:
                continue
            curr.append((l.val, i))
 
        heapq.heapify(curr)
 
        while curr:
            min_val, i = heapq.heappop(curr)
            head.next = ListNode(min_val)
            head = head.next
            if lists[i].next:
                lists[i] = lists[i].next
                heapq.heappush(curr, (lists[i].val, i))
 
        return res.next