一、题目描述

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

示例:

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

二、解题思路 & 代码

用 优先队列 (堆) 来实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def mergeKLists(self, lists: List[ListNode]) -> ListNode:if not lists:return Noneimport heapqheap = []# 首先 for 嵌套 while 就是将所有元素都取出来放入堆中for node in lists:while node:heapq.heappush(heap, node.val)node = node.nextdummy = ListNode(None)cur = dummy# 依次将堆中的元素取出（因为是小顶堆，所以每次取出来的都是目前堆中最小的元素）# 而后重新构建一个列表返回while heap:tmp_node = ListNode(heappop(heap))cur.next = tmp_nodecur = tmp_nodereturn dummy.next

1. 空间复杂度 $O(k)$
2. 时间复杂度 $O(nlog(k))$；$n$ 是所有节点个数，$k$ 是链表数

参考：

1. LeetCode题解