[leetcode hot 150]第二十三题，合并K个升序链表
题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [1->4->5,1->3->4,2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
这题虽然是困难题，但是思路很清晰，很好理解，主要借助最小堆，因为最小堆有着将最小的元素置为堆顶的性质，所以每次取最小值时将最小堆的头推出即可。
并且使用dummy作为结果的头结点返回。代码及思路如下：
- 创建最小堆：
- 使用
PriorityQueue作为最小堆，并定义比较器来比较节点的值。- 初始化最小堆：
- 遍历所有链表，将每个链表的头节点（如果不为空）加入最小堆。
- 创建结果链表：
- 使用一个哑节点（dummy node）来简化头节点的处理。
- 合并过程：
- 当最小堆不为空时，重复以下步骤：
a. 从堆中取出值最小的节点。
b. 将这个节点添加到结果链表的末尾。
c. 如果这个节点还有下一个节点，将下一个节点加入堆中。- 返回结果：
- 返回哑节点的下一个节点，即合并后链表的真正头节点。
复杂度分析
- 时间复杂度：O(N log K)，其中 N 是所有节点的总数，K 是链表的数量。
每个节点都会被加入和取出堆一次，每次堆操作的时间复杂度是 O(log K)。- 空间复杂度：O(K)，优先队列中最多同时存在 K 个节点。
import java.util.Comparator;
import java.util.PriorityQueue;public class no_23 {public static void main(String[] args) {ListNode l1 = new ListNode(1, new ListNode(4, new ListNode(5)));ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));ListNode l3 = new ListNode(2, new ListNode(6));ListNode[] lists = {l1, l2, l3};// 合并链表ListNode result = mergeKLists(lists);// 打印结果while (result != null) {System.out.print(result.val + " ");result = result.next;}}public static ListNode mergeKLists(ListNode[] lists) {// 最小堆PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));// 将所有的链表头节点加入最小堆for (ListNode head : lists) {if (head != null) {minHeap.offer(head);}}ListNode dummy = new ListNode(0);ListNode tail = dummy;while (!minHeap.isEmpty()) {ListNode node = minHeap.poll();tail.next = node;tail = tail.next;if (node.next != null) {minHeap.offer(node.next);}}return dummy.next;}
}
class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}