当前位置：首页 > web >正文

【LeetCode 热题 100】23. 合并 K 个升序链表——（解法一）逐一合并

web 2025/7/14 13:06:28

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(K * N)
- 空间复杂度：O(1)

整体思路

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

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

其核心逻辑步骤如下：

处理边界情况：
- 首先，检查输入的链表数组 lists 是否为 null 或空。如果是，直接返回 null。
- 如果数组中只有一个链表，直接返回该链表。
迭代合并：
- 算法将 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 次。
merge 辅助函数：
- 这个私有函数 merge(l1, l2) 是一个标准的“合并两个有序链表”的实现。
- 它使用哨兵节点 dummy 和一个 cur 指针，通过迭代比较 l1 和 l2 的节点值，将较小的节点链接到结果链表的末尾，直到其中一个链表被遍历完。
- 最后，将另一个链表中剩余的部分直接追加到结果链表的末尾。
- 这个函数在每次主循环中被调用。
返回结果：
- 当 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)

merge 函数的复杂度：合并两个长度分别为 m 和 n 的链表，时间复杂度是 O(m + n)。
主循环分析：
- 设 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)。