一、题目描述给定一个链表数组每个链表都已经按升序排列。请将所有链表合并到一个升序链表中返回合并后的链表。示例 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示例 2输入lists [] 输出[]示例 3输入lists [[]] 输出[]提示k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按升序排列lists[i].length 的总和不超过 10^4二、解题思路总览核心思想分治归并自底向上本题有多种解法优先级队列堆分治归并本题代码采用的是分治归并思路和第 148 题排序链表是同一套思想只是扩展到了 K 个链表。方法核心思路时间复杂度空间复杂度堆优先级队列每次从 K 个链表头取最小O(n log k)O(k)分治归并两两合并逐层翻倍O(n log k)O(log k)时间复杂度两者相同分治归并的优势是不需要额外的数据结构。三、完整代码classSolution{// 合并两个有序链表与第 21 题完全相同ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){ListNode*dummynewListNode(0);ListNode*curdummy;while(list1list2){if(list1-vallist2-val){cur-nextlist2;list2list2-next;}else{cur-nextlist1;list1list1-next;}curcur-next;}cur-nextlist1?list1:list2;returndummy-next;}public:ListNode*mergeKLists(vectorListNode*lists){intmlists.size();if(m0)returnNULL;// 按步长翻倍进行两两合并for(intstep1;stepm;step*2){for(inti0;istepm;istep*2){lists[i]mergeTwoLists(lists[i],lists[istep]);}}returnlists[0];}};四、算法流程图4.1 mergeKLists 主函数流程输入链表数组 lists长度为 m [Step 1] 判断边界 | v m 0 |是 |否 v v 返回 NULL [Step 2] 继续 | v 【按步长翻倍进行两两合并】 | v step 1 | v step m 成立 |否 v 【返回 lists[0]】 | v 【外层循环step * 2】 | v step m 成立 |否 |是 v v 【返回】 [Step 3] 内层循环 | v i 0 | v i step m |否 v 【内层循环结束】 | v i step * 2 | v 回到 i step m 判断4.2 两两合并流程step 1 的第一轮初始状态lists [L0, L1, L2, L3, L4, L5, L6, L7] step 1 时 i 0: lists[0] merge(L0, L1) i 2: lists[2] merge(L2, L3) i 4: lists[4] merge(L4, L5) i 6: lists[6] merge(L6, L7) 合并过程 L0 - 1 - 4 - 5 L1 - 1 - 3 - 4 merge 得到1 - 1 - 3 - 4 - 4 - 5 结果lists [合并后L01, 合并后L23, 合并后L45, 合并后L67, L4, L5, L6, L7]4.3 完整合并树状流程8 个链表的例子初始状态 lists[0] 1-4-5 lists[1] 1-3-4 lists[2] 2-6 lists[3] 7-8-9 lists[4] 10-11 lists[5] 12-13 lists[6] 14-15 lists[7] 16-17 step 1第一轮两两合并 merge(lists[0], lists[1]) -- 1-1-3-4-4-5 merge(lists[2], lists[3]) -- 2-6-7-8-9 merge(lists[4], lists[5]) -- 10-11-12-13 merge(lists[6], lists[7]) -- 14-15-16-17 step 2第二轮两两合并 merge(lists[0], lists[2]) -- 1-1-2-3-4-4-5-6-7-8-9 merge(lists[4], lists[6]) -- 10-11-12-13-14-15-16-17 step 4第三轮两两合并 merge(lists[0], lists[4]) -- 最终结果4.4 合并两个有序链表示意图输入list1 1-3-5-7 list2 2-4-6-8 初始化 dummy - NULL cur - dummy list1 - 1-3-5-7 list2 - 2-4-6-8 第一轮比较1 2 cur-next list1 (1) cur cur-next list1 list1-next (指向3) 第二轮比较3 2 cur-next list2 (2) cur cur-next list2 list2-next (指向4) 第三轮比较3 4 cur-next list1 (3) ... 重复直到 list1 和 list2 全部处理完 结果1-2-3-4-5-6-7-8五、逐行解析5.1 mergeTwoLists合并两个有序链表原理创建 dummy 哑节点简化边界处理用 cur 遍历比较两个链表的当前节点小的节点接入新链表最后把剩余的部分直接接上去循环条件while (list1 list2)选择逻辑if list1-val list2-val: 选 list2 else: 选 list1收尾cur-next list1 ? list1 : list2将剩余非空链表直接接入5.2 mergeKLists 主函数核心逻辑外层循环控制合并间隔for (int step 1; step m; step * 2) 每轮 step 翻倍1, 2, 4, 8, ... 每轮内部 for (int i 0; i step m; i step * 2) lists[i] merge(lists[i], lists[i step])为什么 step m当 step m 时说明所有链表已经合并完毕不需要继续。为什么 i step m第 i 个链表要和第 i step 个链表合并如果 i step m说明第 i step 个链表不存在不需要合并。六、复杂度分析6.1 时间复杂度推导假设有 K 个链表总节点数为 N。 第一轮step 1合并 K/2 组每组合并约 2 个节点 第二轮step 2合并 K/4 组每组合并约 4 个节点 第三轮step 4合并 K/8 组每组合并约 8 个节点 ... 总合并次数 K/2 K/4 K/8 ... K 每轮总工作量 O(N) 总轮数 log K 总时间 O(N log K)指标复杂度说明时间复杂度O(N log K)N 为总节点数K 为链表个数空间复杂度O(log K)递归栈深度本题用迭代无递归栈6.2 对比三种解法解法时间空间特点逐个合并O(KN)O(1)每次合并后还要和下一个合并堆优先级队列O(N log K)O(K)需要维护大小为 K 的堆分治归并本题O(N log K)O(log K)无需额外数据结构七、面试追问问题回答要点分治归并的时间复杂度是多少O(N log K)N 是总节点数K 是链表个数为什么不用逐个合并逐个合并是 O(KN)K 个链表需要合并 K-1 次每次 O(N)堆解法和分治解法哪个更好时间复杂度相同分治解法空间更优不需要堆为什么 step 要翻倍保证每轮合并后链表数量减半最终收敛到 1i step * 2 是什么意思每次跳过一个完整的合并区间进入下一个区间如果 K 不是 2 的幂次怎么办i step m 会自动处理边界只合并存在的配对i step m 而不是 i m - step两者等价前者更简洁直观能否用递归实现分治可以但迭代版本更省空间避免递归栈八、相关题目题号题目关键点21合并两个有序链表mergeTwoLists 基础版23合并 K 个升序链表本题148排序链表归并排序在链表上的应用143重排链表先找中点再合并234回文链表快慢指针找中点876链表的中间节点快慢指针九、总结要点内容核心思想分治归并两两合并逐层翻倍关键循环外层 step * 2内层 i step * 2合并函数与第 21 题完全相同的 mergeTwoLists复杂度时间 O(N log K)空间 O(log K)记忆口诀步长翻倍、两两合并、收敛到一
【力扣100题】20.合并 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示例 2输入lists [] 输出[]示例 3输入lists [[]] 输出[]提示k lists.length0 k 10^40 lists[i].length 500-10^4 lists[i][j] 10^4lists[i] 按升序排列lists[i].length 的总和不超过 10^4二、解题思路总览核心思想分治归并自底向上本题有多种解法优先级队列堆分治归并本题代码采用的是分治归并思路和第 148 题排序链表是同一套思想只是扩展到了 K 个链表。方法核心思路时间复杂度空间复杂度堆优先级队列每次从 K 个链表头取最小O(n log k)O(k)分治归并两两合并逐层翻倍O(n log k)O(log k)时间复杂度两者相同分治归并的优势是不需要额外的数据结构。三、完整代码classSolution{// 合并两个有序链表与第 21 题完全相同ListNode*mergeTwoLists(ListNode*list1,ListNode*list2){ListNode*dummynewListNode(0);ListNode*curdummy;while(list1list2){if(list1-vallist2-val){cur-nextlist2;list2list2-next;}else{cur-nextlist1;list1list1-next;}curcur-next;}cur-nextlist1?list1:list2;returndummy-next;}public:ListNode*mergeKLists(vectorListNode*lists){intmlists.size();if(m0)returnNULL;// 按步长翻倍进行两两合并for(intstep1;stepm;step*2){for(inti0;istepm;istep*2){lists[i]mergeTwoLists(lists[i],lists[istep]);}}returnlists[0];}};四、算法流程图4.1 mergeKLists 主函数流程输入链表数组 lists长度为 m [Step 1] 判断边界 | v m 0 |是 |否 v v 返回 NULL [Step 2] 继续 | v 【按步长翻倍进行两两合并】 | v step 1 | v step m 成立 |否 v 【返回 lists[0]】 | v 【外层循环step * 2】 | v step m 成立 |否 |是 v v 【返回】 [Step 3] 内层循环 | v i 0 | v i step m |否 v 【内层循环结束】 | v i step * 2 | v 回到 i step m 判断4.2 两两合并流程step 1 的第一轮初始状态lists [L0, L1, L2, L3, L4, L5, L6, L7] step 1 时 i 0: lists[0] merge(L0, L1) i 2: lists[2] merge(L2, L3) i 4: lists[4] merge(L4, L5) i 6: lists[6] merge(L6, L7) 合并过程 L0 - 1 - 4 - 5 L1 - 1 - 3 - 4 merge 得到1 - 1 - 3 - 4 - 4 - 5 结果lists [合并后L01, 合并后L23, 合并后L45, 合并后L67, L4, L5, L6, L7]4.3 完整合并树状流程8 个链表的例子初始状态 lists[0] 1-4-5 lists[1] 1-3-4 lists[2] 2-6 lists[3] 7-8-9 lists[4] 10-11 lists[5] 12-13 lists[6] 14-15 lists[7] 16-17 step 1第一轮两两合并 merge(lists[0], lists[1]) -- 1-1-3-4-4-5 merge(lists[2], lists[3]) -- 2-6-7-8-9 merge(lists[4], lists[5]) -- 10-11-12-13 merge(lists[6], lists[7]) -- 14-15-16-17 step 2第二轮两两合并 merge(lists[0], lists[2]) -- 1-1-2-3-4-4-5-6-7-8-9 merge(lists[4], lists[6]) -- 10-11-12-13-14-15-16-17 step 4第三轮两两合并 merge(lists[0], lists[4]) -- 最终结果4.4 合并两个有序链表示意图输入list1 1-3-5-7 list2 2-4-6-8 初始化 dummy - NULL cur - dummy list1 - 1-3-5-7 list2 - 2-4-6-8 第一轮比较1 2 cur-next list1 (1) cur cur-next list1 list1-next (指向3) 第二轮比较3 2 cur-next list2 (2) cur cur-next list2 list2-next (指向4) 第三轮比较3 4 cur-next list1 (3) ... 重复直到 list1 和 list2 全部处理完 结果1-2-3-4-5-6-7-8五、逐行解析5.1 mergeTwoLists合并两个有序链表原理创建 dummy 哑节点简化边界处理用 cur 遍历比较两个链表的当前节点小的节点接入新链表最后把剩余的部分直接接上去循环条件while (list1 list2)选择逻辑if list1-val list2-val: 选 list2 else: 选 list1收尾cur-next list1 ? list1 : list2将剩余非空链表直接接入5.2 mergeKLists 主函数核心逻辑外层循环控制合并间隔for (int step 1; step m; step * 2) 每轮 step 翻倍1, 2, 4, 8, ... 每轮内部 for (int i 0; i step m; i step * 2) lists[i] merge(lists[i], lists[i step])为什么 step m当 step m 时说明所有链表已经合并完毕不需要继续。为什么 i step m第 i 个链表要和第 i step 个链表合并如果 i step m说明第 i step 个链表不存在不需要合并。六、复杂度分析6.1 时间复杂度推导假设有 K 个链表总节点数为 N。 第一轮step 1合并 K/2 组每组合并约 2 个节点 第二轮step 2合并 K/4 组每组合并约 4 个节点 第三轮step 4合并 K/8 组每组合并约 8 个节点 ... 总合并次数 K/2 K/4 K/8 ... K 每轮总工作量 O(N) 总轮数 log K 总时间 O(N log K)指标复杂度说明时间复杂度O(N log K)N 为总节点数K 为链表个数空间复杂度O(log K)递归栈深度本题用迭代无递归栈6.2 对比三种解法解法时间空间特点逐个合并O(KN)O(1)每次合并后还要和下一个合并堆优先级队列O(N log K)O(K)需要维护大小为 K 的堆分治归并本题O(N log K)O(log K)无需额外数据结构七、面试追问问题回答要点分治归并的时间复杂度是多少O(N log K)N 是总节点数K 是链表个数为什么不用逐个合并逐个合并是 O(KN)K 个链表需要合并 K-1 次每次 O(N)堆解法和分治解法哪个更好时间复杂度相同分治解法空间更优不需要堆为什么 step 要翻倍保证每轮合并后链表数量减半最终收敛到 1i step * 2 是什么意思每次跳过一个完整的合并区间进入下一个区间如果 K 不是 2 的幂次怎么办i step m 会自动处理边界只合并存在的配对i step m 而不是 i m - step两者等价前者更简洁直观能否用递归实现分治可以但迭代版本更省空间避免递归栈八、相关题目题号题目关键点21合并两个有序链表mergeTwoLists 基础版23合并 K 个升序链表本题148排序链表归并排序在链表上的应用143重排链表先找中点再合并234回文链表快慢指针找中点876链表的中间节点快慢指针九、总结要点内容核心思想分治归并两两合并逐层翻倍关键循环外层 step * 2内层 i step * 2合并函数与第 21 题完全相同的 mergeTwoLists复杂度时间 O(N log K)空间 O(log K)记忆口诀步长翻倍、两两合并、收敛到一
