23. 合并K个排序链表 [hard]

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

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

通过次数139,112 | 提交次数266,691

First Try

2020-07-06

本来觉得需要遍历，但一看每个元素遍历一波岂不是n k,有点弱鸡。不如直接上高级数据结构优先队列，每个元素只需要lgk,这样总的就是n lgK。然后继续使用dummy元素在队首做辅助，同时记录新的列表的head和tail节点，每次在tail后面添加新元素就行，整个思路就非常清晰了。

自从之前领略到优先队列的好处，现在使用频率高多了。以前总理解不了，分明有各种排序算法，还要优先队列二叉堆干啥。其实优先队列用来处理随时动态更新的排序特别有效。

这道题应该还有更快的合并排序方法，比如每次先在一条最小的队列上一路怼，看能怼多远，估计会快一点点。先不管了，还是用正规军思路清晰的方法来，优化过度反而影响阅读。

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

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for link in lists:
            if not link:
                continue
            dummy = ListNode(None)
            dummy.next = link
            n = link.val
            heapq.heappush(heap, [n, dummy])
        head = pre = ListNode(None)
        while len(heap):
            _, link = heapq.heappop(heap)
            node = link.next 
            link.next = node.next
            pre.next = node 
            pre = node 
            if node.next is not None:
                heapq.heappush(heap, [node.next.val, link])
        return head.next 

执行用时：80 ms, 在所有 Python 提交中击败了64.68%的用户
内存消耗：21.6 MB, 在所有 Python 提交中击败了18.75%的用户

23. 合并K个排序链表 [hard]​

First Try​

23. 合并K个排序链表 [hard]

First Try