Problem: 23. 合并 K 个升序链表
题目：给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

整体思路

这段代码旨在解决一个经典的链表问题：合并 K 个排序链表 (Merge K Sorted Lists)。问题要求将一个包含 K 个已排序链表的数组，合并成一个单一的、大的有序链表。

该实现采用了一种简单直接的 逐一合并 (One by One Merging) 的策略。它将“合并K个链表”的问题，简化为了“重复执行 K-1 次‘合并两个链表’”的问题。

其核心逻辑步骤如下：

1. 处理边界情况：

   • 首先，检查输入的链表数组 lists 是否为 null 或空。如果是，直接返回 null。
   • 如果数组中只有一个链表，直接返回该链表。

2. 迭代合并：

   • 算法将 lists[0] 作为“累加器”或“基准链表”。
   • 通过一个 for 循环，从 i=1 开始，依次将 lists[i] 合并到 lists[0] 中。
   • lists[0] = merge(lists[0], lists[i]); 这一行是核心。它调用一个辅助函数 merge，将当前的合并结果 lists[0] 与下一个链表 lists[i] 进行合并，然后用新的、更长的合并结果来更新 lists[0]。
   • 这个过程会重复 K-1 次。

3. merge 辅助函数：

   • 这个私有函数 merge(l1, l2) 是一个标准的“合并两个有序链表”的实现。
   • 它使用哨兵节点 dummy 和一个 cur 指针，通过迭代比较 l1 和 l2 的节点值，将较小的节点链接到结果链表的末尾，直到其中一个链表被遍历完。
   • 最后，将另一个链表中剩余的部分直接追加到结果链表的末尾。
   • 这个函数在每次主循环中被调用。

4. 返回结果：

   • 当 for 循环结束后，lists[0] 中就存储了所有 K 个链表合并后的最终结果，将其返回。

虽然这个方法逻辑清晰，易于理解，但它并不是最高效的解决方案，因为在合并过程中存在大量的重复比较。

完整代码

/*** Definition for singly-linked list.*/
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {/*** 合并 K 个排序链表。* @param lists 一个包含 K 个排序链表的数组* @return 合并后的单一排序链表*/public ListNode mergeKLists(ListNode[] lists) {// 处理边界情况：输入为空或没有链表if (null == lists || lists.length == 0) {return null;}int n = lists.length;// 如果只有一个链表，直接返回它if (1 == n) {return lists[0];}// 步骤 1: 逐一合并// 将 lists[0] 作为基础，依次将 lists[1], lists[2], ... 合并进来for (int i = 1; i < n; i++) {// 调用辅助函数合并当前的累积结果 lists[0] 和下一个链表 lists[i]lists[0] = merge(lists[0], lists[i]);}// 循环结束后，lists[0] 就是最终的合并结果return lists[0];}/*** 辅助函数：合并两个有序链表。* @param l1 第一个有序链表* @param l2 第二个有序链表* @return 合并后的有序链表*/private ListNode merge(ListNode l1, ListNode l2) {// 使用哨兵节点简化合并逻辑ListNode dummy = new ListNode();ListNode cur = dummy;// 比较两个链表的节点，将较小的链接到结果链表while (null != l1 && null != l2) {if (l1.val < l2.val) {cur.next = l1;l1 = l1.next;} else {cur.next = l2;l2 = l2.next;}cur = cur.next;}// 将剩余的链表部分直接追加到末尾cur.next = null == l1 ? l2 : l1;return dummy.next;}
}

时空复杂度

时间复杂度：O(K * N)

1. merge 函数的复杂度：合并两个长度分别为 m 和 n 的链表，时间复杂度是 O(m + n)。
2. 主循环分析：
   • 设 K 是链表的数量，N 是所有链表的节点总数。为简化分析，我们假设每个链表平均有 N/K 个节点。
   • 第一次合并 (i=1): merge(lists[0], lists[1])。lists[0] 长度为 N/K，lists[1] 长度为 N/K。耗时 O(2N/K)。合并后 lists[0] 长度变为 2N/K。
   • 第二次合并 (i=2): merge(lists[0], lists[2])。lists[0] 长度为 2N/K，lists[2] 长度为 N/K。耗时 O(3N/K)。合并后 lists[0] 长度变为 3N/K。
   • …
   • 第 i 次合并: lists[0] 长度为 i * (N/K)，lists[i] 长度为 N/K。耗时 O((i+1)N/K)。
   • 总时间 ≈ Σ(i=1 to K-1) (i+1)N/K = (N/K) * Σ(j=2 to K) j = (N/K) * (K(K+1)/2 - 1)。
   • 这个表达式的最高阶项是 (N/K) * (K^2 / 2)，所以复杂度是 O(N * K)。

综合分析：
该算法的时间复杂度为 O(N * K)，其中 N 是总节点数，K 是链表数。当 K 较大时，这个效率并不理想。

空间复杂度：O(1)

1. 主要存储开销：
   • merge 函数内部使用了 dummy 和 cur 等常数个指针变量。
   • 主函数 mergeKLists 也没有使用与 N 或 K 成比例的额外数据结构。它是在原地修改 lists 数组的第一个元素。

综合分析：
算法所需的额外辅助空间是常数级别的。因此，其空间复杂度为 O(1)。这是该解法的一个优点。