本题出处为LeetCode 23题，难度为困难。

问题⌗

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

示例:

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

解法⌗

  1. 链表已经有序，可以读取每个链表中的第一个元素，一共K个元素，选出其中的最小值，将该元素加入到新的链表中并从原来的链表中删除。一共执行N次，最终构建出新的有序链表。
  2. 如果每次从K个元素中选出最小值，单次的时间复杂度为O(N)，总的时间复杂度为O(KN)，有优化空间。可以将K个元素放入堆中。每次从堆顶取出一个元素，因为堆序关系，每次取出的元素是堆中的最小值。然后继续将该元素的下一个元素加入堆中，每次加入的时间复杂度是O(logK)，一共执行N次，所以复杂度降为O(NlogK)。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy_head = ListNode(0)
        ptr = dummy_head
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i))
                lists[i] = node.next

        while heap:
            val, i = heapq.heappop(heap)
            ptr.next = ListNode(val)
            ptr = ptr.next
            node = lists[i]
            if node:
                lists[i] = node.next
                heapq.heappush(heap, (node.val, i))
        return dummy_head.next

复杂度分析⌗

设N为数组中元素的总数，K为数组的个数。

  • 时间复杂度 O(NlogK)
    • 每次heappush复杂度 O(logK)，总共执行N次。
  • 空间复杂度 O(N)
    • 创建新的链表需要分配N个内存空间，创建堆需要分配K个内存空间，K<=N，最终为 O(N)。