[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作为结果的头结点返回。代码及思路如下：

1. 创建最小堆：
   • 使用 PriorityQueue 作为最小堆，并定义比较器来比较节点的值。
2. 初始化最小堆：
   • 遍历所有链表，将每个链表的头节点（如果不为空）加入最小堆。
3. 创建结果链表：
   • 使用一个哑节点（dummy node）来简化头节点的处理。
4. 合并过程：
   • 当最小堆不为空时，重复以下步骤：
     a. 从堆中取出值最小的节点。
     b. 将这个节点添加到结果链表的末尾。
     c. 如果这个节点还有下一个节点，将下一个节点加入堆中。
5. 返回结果：
   • 返回哑节点的下一个节点，即合并后链表的真正头节点。

 复杂度分析

• 时间复杂度：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;}
}