23. 合并K个排序链表

解法很多

1. 将所有的 ListNode放到数组中,然后排序, 再输出
2. 变为2路合并

题眼

这个题目就是考察的堆. python 中的heapq

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        
        heap = []
        dummy_node = ListNode(0)
        cur_node = dummy_node
        # 初始化heap
        for node in lists:
            if node!=None:
                heap.append((node.val,node))
        heapq.heapify(heap)
        # 开始一个一个出队列
        # 一个一个入队列
        while heap:
            pop = heapq.heappop(heap)
            cur_node.next = ListNode(pop[0])
            cur_node = cur_node.next
            if pop[1].next:    
                heapq.heappush(heap,(pop[1].next.val,pop[1].next))
        return dummy_node.next