Python 解LeetCode：23. Merge k Sorted Lists

• 题目描述：把k个排序的链表组成的列表合并成一个排序的链表

• 思路：

1. 使用堆排序，遍历列表，把每个列表中链表的头指针的值和头指针本身作为一个元素放在堆中；
2. 第一步中遍历完列表后，此时堆中最多会有n个元素，n是列表的长度；
3. 当堆不为空，取出堆中的最小值，然后把该值的指针指向下一个元素，并入堆；
4. 第3步可以确保堆永远是o(n)大小的；
5. 堆为空返回头结点就可以了

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq
        min_heap = []
        ret = head = ListNode(0)
        for k, link in enumerate(lists):
            if link:
                heapq.heappush(min_heap, [link.val, link])
        while min_heap:
            cur = heapq.heappop(min_heap)
            ret.next = cur[-1]
            ret = ret.next
            if ret.next:
                heapq.heappush(min_heap, [ret.next.val, ret.next])
        return head.next