方法一:最小堆
1. 思路
(1)合并后的第一个节点 first,一定是某个链表的头节点(因为链表已按升序排列)。
(2)合并后的第二个节点,可能是某个链表的头节点,也可能是 first 的下一个节点。
举例:有 3 个链表 1->2->5,3->4->6,4->5->6。找到第一个节点 1 之后,第二个节点不是另一个链表的头节点,而是节点 1 的下一个节点 2。
(3)按照上面的过程继续思考,每当我们找到一个节点值最小的节点 x,就把节点 x.next 加入'可能是最小节点'的集合中。
(4)因此需要一个数据结构,它需要支持:
——能从数据结构中找到并移除最小节点。
——能插入节点。
(5)可以用最小堆实现。初始把所有链表的头节点加入堆,然后不断弹出堆中最小的节点 x,如果 x.next 不为空就加入堆中,循环直到堆为空。把弹出的节点按顺序拼接起来,就得到了答案。
(6)实现时,可用哨兵节点简化代码。
2. 复杂度分析
(1)时间复杂度:O(Llogm),其中 m 为 lists 的长度,L 为所有链表的长度之和。
(2)空间复杂度:O(m),堆中至多有 m 个元素。
附代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) {
if (head != null) {
heap.add(head);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) {
heap.add(node.next);
}
}
return dummy.next;
}
}

