6.22 - hard - 3

23. Merge k Sorted Lists
用heap可以直接做出来。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        # 这题的第一直觉用heap
        dummyhead = ListNode(0)
        head = dummyhead
        heap = []
        
        #初始化
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, lists[i], i))
                lists[i] = lists[i].next

        # 循环直到heap为空
        while heap:
            _, node, i = heapq.heappop(heap)
            head.next = node
            head = head.next
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, lists[i], i))
                lists[i] = lists[i].next
            
        
        return dummyhead.next