023._merge_k_sorted_lists.md

###23. Merge k Sorted Lists

题目: https://leetcode.com/problems/merge-k-sorted-lists/

难度: Hard

思路：

看到思路有heap，similar question有ugly number|| -> 这个是用heapq来解决的

看一下heapq的docment界面和例子：

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)

那么就用heap:

a1 -> a2 -> a3
b1 -> b2 -> b3
c1 -> c2 -> c3

我们先把a1, b1, c1放入minheap中，然后我们pop一个，这个必定是最小的，同时我们把最小的这个下一个放入heap中，这样再次pop，就能得到第二小，逐渐这样做，把它们连起来就能得到有序的list了。

写到这里瞬间明白和ugly number ii像的点了，甚至感觉跟find in sorted matrix ii也像

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq
        h = []

        for listhead in lists:
            if listhead:
                # here we use val as key, and node as the 'task'
                heapq.heappush(h, (listhead.val,listhead))

        cur = ListNode(-1)
        dummy = cur

        while h:
            # we pop out both val annd node
            _, smallestNode = heapq.heappop(h)
            cur.next = smallestNode
            cur = cur.next
            if smallestNode.next:
                heapq.heappush(h, (smallestNode.next.val,smallestNode.next))
        return dummy.next

当然类似的有 merge two sorted list

之所以要用到heap大概是每次我们都需要维持一个最小的状态。