Heap

23. Merge k Sorted Lists

class Solution(object):
    def mergeKLists(self, lists):
        curr = dummy = ListNode(None)
        heap = [(node.val, i, node) for i,node in enumerate(lists) if node is not None]
        i = len(lists)
        heapq.heapify(heap)
        while heap:
            _, _,node = heapq.heappop(heap)
            curr.next = node
            curr = node
            if node.next is not None:
                heapq.heappush(heap, (node.next.val, i, node.next))
                i += 1
        return dummy.next