合并两个升序链表 与 合并k个升序链表

Ne0inhk

— 12 min read
合并两个升序链表 与 合并k个升序链表

玩转链表合并✨：从 2 个到 k 个升序链表的通关秘籍

在算法面试的高频题库里，链表相关题目一直是 “常客”，而 “升序链表合并” 更是其中的经典题型 —— 从基础的「合并两个升序链表」，到进阶的「合并 k 个升序链表」，难度层层递进，却也藏着通用的解题逻辑。今天就带大家拆解这两道题，从核心思路到代码实现，再到面试官常问的 “灵魂拷问”，一次性吃透✨！

leetcode链接：

合并两个有序链表

 合并 K 个升序链表

一、合并两个升序链表：基础版 “链表拼接术” 📌

给定两个升序排列的单链表，要求合并成一个新的升序链表并返回头节点。这道题是链表合并的 “入门款”，掌握它的核心逻辑，才能轻松应对后续的 k 个链表合并。

1. 解题关键：3 个 “核心武器”

想要优雅解决这道题，离不开三个关键设计，少一个都可能让边界处理变得繁琐：

  • 🛡️ 哨兵节点（dummy）：值通常设为 - 1（无实际意义），作用是 “简化边界处理”。比如当两个链表都为空、或其中一个为空时，不用单独判断头节点，直接返回dummy.next即可。
  • 📌 动态指针（cur）：初始指向哨兵节点，相当于 “拼接工人”，负责把选中的节点接在新链表后面，每拼接一个节点就向后移动一步。
  • 🔍 双指针（p1、p2）：分别指向两个链表的当前遍历节点，是 “决策核心”。通过比较p1.val和p2.val，决定该拼接哪个节点，直到其中一个链表遍历完毕。

具体执行逻辑：① 双指针同步遍历，while循环条件是p1和p2都不为空；② 若p1.val ≤ p2.val，把p1接在cur.next，同时p1后移；反之则拼接p2，p2后移；③ 每轮循环结束后，cur后移一步，准备接下一个节点；④ 循环结束后，必有一个链表还有剩余节点（本身有序），直接把剩余链表接在cur.next即可，无需逐个遍历。

2. 代码展示

JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并两个升序有序链表，返回新的升序链表头节点 * @param {ListNode} list1 - 第一个升序有序链表头节点 * @param {ListNode} list2 - 第二个升序有序链表头节点 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeTwoLists = function (list1, list2) { // 哨兵节点（哑节点）：简化空链表等边界情况处理 let dummy = new ListNode(-1); // 动态指针：负责拼接新节点，初始指向哨兵节点 let cur = dummy; // 双指针：分别遍历两个输入链表 let p1 = list1, p2 = list2; // 双指针同步遍历，直到其中一个链表遍历完毕 while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { // 拼接p1节点，p1指针后移 cur.next = p1; p1 = p1.next; } else { // 拼接p2节点，p2指针后移 cur.next = p2; p2 = p2.next; } // 动态指针后移，准备拼接下一个节点 cur = cur.next; } // 处理剩余节点：直接拼接未遍历完的链表（链表本身有序） cur.next = p1 !== null ? p1 : p2; // 哨兵节点的next是合并后链表的真实头节点 return dummy.next; };
JAVA 版本

java

/** * Definition for singly-linked list. * public 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 { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 哨兵节点（哑节点）：简化边界处理 ListNode dummy = new ListNode(-1); // 动态指针：负责拼接新节点 ListNode cur = dummy; // 双指针：遍历两个输入链表 ListNode p1 = list1, p2 = list2; // 双指针同步遍历，直到其中一个链表遍历完毕 while (p1 != null && p2 != null) { if (p1.val <= p2.val) { // 拼接p1节点，p1后移 cur.next = p1; p1 = p1.next; } else { // 拼接p2节点，p2后移 cur.next = p2; p2 = p2.next; } // 动态指针后移 cur = cur.next; } // 拼接剩余未遍历完的链表 cur.next = p1 != null ? p1 : p2; // 返回合并后链表的真实头节点 return dummy.next; } }

二、合并 k 个升序链表：进阶版 “分治优化术” 🚀

当链表数量从 2 个变成 k 个，直接套用 “两两合并” 的暴力思路虽然可行，但时间复杂度会飙升。这道题的核心是 “优化时间复杂度”，而分治思想是最优解的关键。

方法一：暴力迭代法（基础版）

1. 解题思路

基于 “合并两个升序链表” 的逻辑，遍历链表数组：先合并第 1 和第 2 个链表得到新链表，再用新链表合并第 3 个，依次类推，直到合并完所有链表。

2. 解题关键
  • 🚫 空值处理：先判断链表数组是否为空，再过滤数组中的空链表（避免空指针异常），过滤后再次判断是否为空；
  • 🧰 哨兵节点 + 动态指针：cur初始指向哨兵节点，且cur.next先指向数组第一个链表，作为每轮合并的 “基础链表”；
  • 🔄 循环合并：for循环遍历过滤后的链表数组，每轮调用mergeTwoLists函数，传入cur.next与当前链表，更新合并结果。
3. 代码展示
JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并k个升序链表（暴力迭代法） * @param {ListNode[]} lists - 升序链表数组 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeKLists = function (lists) { // 判空：链表数组为空直接返回null if (lists.length === 0) return null; // 过滤空链表：避免后续合并时出现空指针 const filterLists = lists.filter(list => list !== null); // 过滤后仍为空，返回null if (filterLists.length === 0) return null; // 哨兵节点：简化边界处理 let dummy = new ListNode(-1); // 动态指针：初始指向第一个链表，作为合并的基础 dummy.next = filterLists[0]; let cur = dummy; // 遍历链表数组，依次合并 for (let i = 1; i < filterLists.length; i++) { // 合并当前基础链表（cur.next）和第i个链表 cur.next = mergeTwoLists(cur.next, filterLists[i]); } // 返回合并后链表头节点 return dummy.next; }; // 复用合并两个升序链表的函数 var mergeTwoLists = function (list1, list2) { let dummy = new ListNode(-1); let cur = dummy; let p1 = list1, p2 = list2; while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 !== null ? p1 : p2; return dummy.next; };
JAVA 版本

java

/** * Definition for singly-linked list. * public 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 { public ListNode mergeKLists(ListNode[] lists) { // 判空：链表数组为空返回null if (lists == null || lists.length == 0) return null; // 过滤空链表 List<ListNode> filterLists = new ArrayList<>(); for (ListNode list : lists) { if (list != null) { filterLists.add(list); } } // 过滤后为空返回null if (filterLists.size() == 0) return null; // 哨兵节点 ListNode dummy = new ListNode(-1); dummy.next = filterLists.get(0); ListNode cur = dummy; // 依次合并链表 for (int i = 1; i < filterLists.size(); i++) { cur.next = mergeTwoLists(cur.next, filterLists.get(i)); } return dummy.next; } // 合并两个升序链表的函数 public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; ListNode p1 = list1, p2 = list2; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 != null ? p1 : p2; return dummy.next; } }

方法二：分治优化法 ⚡

暴力迭代法虽然容易理解，但时间复杂度太高，面试中面试官大概率会追问 “如何优化”—— 这时候分治思想就是最优解。

1. 解题思路：先拆后合，降低时间复杂度
① 暴力法时间复杂度分析

假设 k 个链表，每个链表有 n 个节点：

  • 第 1 次合并：合并 2 个链表，耗时 O (2n)；
  • 第 2 次合并：合并（2n）和 n，耗时 O (3n)；
  • …
  • 第 k-1 次合并：耗时 O (kn)；总时间：O(2n + 3n + ... + kn) = O(n*k(k+1)/2 -n) ≈ O(k²n)。举例：k=4，n=2 → 总时间≈O (16n)（22 +32 +4*2=18≈16）。
② 分治法思路

分治的核心是 “分而治之”：把 k 个链表两两分组，合并后得到 k/2 个链表；再把这 k/2 个链表两两分组，合并后得到 k/4 个；直到最终合并成 1 个链表。

③ 分治法时间复杂度分析

每一轮合并的总耗时都是 O (kn)（所有节点仅遍历一次），合并轮数是log₂k（比如 k=4，轮数 = 2；k=8，轮数 = 3）。总时间：O(kn logk)。举例：k=4，n=2 → 总时间 = O (242)=O (16)（k 越大差距越明显：k=100，暴力法≈O (10000n)，分治法≈O (200n)）。

2. 解题关键：分治递归
  • 📌 递归出口：当分治的左边界 = 右边界（left===right），说明只剩一个链表，直接返回；
  • 🎯 找中点：mid = left + Math.floor((right-left)/2)，避免溢出；
  • ✂️ 拆分：递归拆分左半部分（left→mid）和右半部分（mid+1→right）；
  • 🧩 合并：调用mergeTwoLists合并左右两部分的结果。
3. 代码展示
JS 版本

javascript

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * 合并k个升序链表（分治法） * @param {ListNode[]} lists - 升序链表数组 * @returns {ListNode} 合并后的升序链表头节点 */ var mergeKLists = function (lists) { // 判空 if (lists.length === 0) return null; // 过滤空链表 lists = lists.filter(list => list !== null); // 再次判空 if (lists.length === 0) return null; // 调用分治函数合并 return merge(lists, 0, lists.length - 1); }; // 分治函数：拆分链表数组并合并 var merge = function (lists, left, right) { // 递归出口：只剩一个链表，直接返回 if (left === right) { return lists[left]; } // 计算中点（避免溢出） let mid = left + Math.floor((right - left) / 2); // 递归拆分左半部分 let leftList = merge(lists, left, mid); // 递归拆分右半部分 let rightList = merge(lists, mid + 1, right); // 合并左右两部分 return mergeTwoLists(leftList, rightList); } // 复用合并两个升序链表的函数 var mergeTwoLists = function (list1, list2) { let dummy = new ListNode(-1); let cur = dummy; let p1 = list1, p2 = list2; while (p1 !== null && p2 !== null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 !== null ? p1 : p2; return dummy.next; }
JAVA 版本

java

/** * Definition for singly-linked list. * public 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 { public ListNode mergeKLists(ListNode[] lists) { // 判空 if (lists == null || lists.length == 0) return null; // 过滤空链表 List<ListNode> filterLists = new ArrayList<>(); for (ListNode list : lists) { if (list != null) { filterLists.add(list); } } // 再次判空 if (filterLists.size() == 0) return null; // 调用分治函数 return merge(filterLists, 0, filterLists.size() - 1); } // 分治函数 private ListNode merge(List<ListNode> lists, int left, int right) { // 递归出口：只剩一个链表 if (left == right) { return lists.get(left); } // 计算中点（避免溢出） int mid = left + (right - left) / 2; // 递归拆分左半部分 ListNode leftList = merge(lists, left, mid); // 递归拆分右半部分 ListNode rightList = merge(lists, mid + 1, right); // 合并左右部分 return mergeTwoLists(leftList, rightList); } // 合并两个升序链表 private ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; ListNode p1 = list1, p2 = list2; while (p1 != null && p2 != null) { if (p1.val <= p2.val) { cur.next = p1; p1 = p1.next; } else { cur.next = p2; p2 = p2.next; } cur = cur.next; } cur.next = p1 != null ? p1 : p2; return dummy.next; } }

面试官会问的 “灵魂拷问” 🤔

  1. 合并两个链表时，为什么要用哨兵节点？不用的话会有什么问题？

答：不用哨兵节点需要单独处理 “头节点为空” 的情况（比如两个链表都为空、或其中一个为空），代码会多出很多边界判断；哨兵节点统一了所有情况，让逻辑更简洁。

  1. 合并 k 个链表的暴力法和分治法时间复杂度差多少？为什么分治法更优？

答：暴力法是O(k²n)，分治法是O(kn logk)；k 越大差距越明显（比如 k=100，暴力法时间是分治法的 50 倍左右）。分治法通过 “两两合并” 减少了重复遍历的节点数，每一轮只遍历所有节点一次，轮数是对数级，因此更优。

  1. 分治法的空间复杂度是多少？能优化吗？

答：递归版分治法的空间复杂度是O(logk)（递归栈的深度）；可以用迭代版分治（非递归）把空间复杂度降到O(1)，但代码会稍复杂。

  1. 除了分治法，合并 k 个链表还有其他方法吗？

答：可以用优先队列（小顶堆）：把每个链表的头节点加入堆，每次弹出最小节点，再把该节点的下一个节点加入堆，直到堆为空。时间复杂度也是O(kn logk)，空间复杂度O(k)。

  1. 处理 k 个链表时，为什么要先过滤空链表？

答：避免空指针异常（比如调用val属性时），也能减少无效的合并操作，提升效率。

结语 📝

从 “合并两个升序链表” 到 “合并 k 个升序链表”，核心逻辑始终是 “两两合并”，区别只在于 “如何组织两两合并的顺序”—— 暴力法是 “顺序合并”，分治法是 “分组合并”。

这两道题的价值不仅在于解题本身，更在于理解 “哨兵节点简化边界”“双指针遍历”“分治优化时间复杂度” 这些通用的算法思想。掌握这些思想，再遇到链表相关的变形题（比如合并有序数组、拆分链表等），也能举一反三✨。

Read more

Flutter 三方库 in_date_utils 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、高效的日期逻辑处理与万年历算法引擎

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 in_date_utils 的鸿蒙化适配指南 - 在鸿蒙系统上构建极致、高效的日期逻辑处理与万年历算法引擎 在鸿蒙（OpenHarmony）系统的日历、任务管理或考勤应用中，如何快速计算某月的天数、判断闰年、或优雅地对日期进行加减操作？in_date_utils 为开发者提供了一套开箱即用的日期增强工具集。本文将深入实战其在鸿蒙生态中的应用。 前言 什么是 in_date_utils？它是 Dart 原生 DateTime 的强力补丁。在 Flutter for OpenHarmony 的实际开发中，我们经常需要处理诸如“上周一的日期”、“本月最后一个周五”等复杂的业务逻辑。利用该库，我们可以避免重复编写琐碎的日期数学运算，让鸿蒙应用的代码更加简洁、易读且稳健。 一、

By Ne0inhk

优选算法——前缀和

👇作者其它专栏 《数据结构与算法》《算法》《C++起始之路》 前缀和相关题解 1.前缀和 算法思路： a.先预处理出来一个【前缀和】数组：         用dp[i]表示：[1,i]区间内所有元素的和，那么dp[i-1]里面存的就是[1,i-1]区间内所有元素的和，那么：可得到递推公式：dp[i]=dp[i-1]+arr[i]； b.使用前缀和数组，【快速】求出【某一个区间内】所有元素的和：         当访问的区间是[l,r]时：区间内所有元素的和为：dp[r]-dp[l-r]。 #include <

By Ne0inhk

无模型自适应控制算法介绍以及与PID对比程序验证

引言 随着工业过程，智能无人系统的快速发展，被控对象的复杂性与日俱增，且逐渐呈现出非线性、强耦合等特点导致系统的数学模型难以精确的建立表达。而传统控制理论需要以被控对象的数学模型为基础，通过机理分析或系统辨识建立精确的数学描述，进而设计控制器以实现期望的控制性能比如PID，MPC等控制方式。在此背景下，数据驱动控制应运而生，其核心思想是直接利用被控系统在线或离线的输入输出数据进行控制器设计。不需要建立显式精确的数学模型。其中，无模型自适应控制 (Model-Free Adaptive Control, MFAC) 理论是1994年由侯忠生教授教授提出，本文后续内容将详细介绍该方法。 无模型自适应控制的基本原理 无模型自适应控制的核心创新在于引入了动态线性化技术及伪偏导数等概念。该方法无需辨识复杂的非线性系统机理模型，而是在每个工作点处，利用受控系统的输入输出数据建立一个等价的虚拟“动态线性化数据模型”，以此逼近原非线性系统在该时刻附近的动态行为。控制器基于此等效模型进行设计，并在线实时更新伪偏导数的估计值，从而实现参数自适应控制乃至结构自适应控制。 关键技术 动态线性化技术

By Ne0inhk
【狂热算法篇】完全背包异次元冒险：容量魔法觉醒，价值风暴来袭！

【狂热算法篇】完全背包异次元冒险：容量魔法觉醒，价值风暴来袭！

欢迎拜访：羑悻的小杀马特.-ZEEKLOG博客 本篇主题：轻轻松松拿捏完全背包问题呀！！！ 制作日期：2026.03.04 隶属专栏：美妙的算法世界 目录 一·问题定义： 二·具体问题演示：  三·动态规划解答完全背包： 3.1非装满状态： 3.1.1状态定义： 3.1.2状态转移方程：   3.1.3初始化： 3.1.4返回值： 3.1.5填充dp表： 3.1.6非装满状态代码总结： 3.1.7非装满状态滚动数组降维优化：  3.2装满状态： 3.2.1状态定义： 3.2.2状态转移方程：  3.

By Ne0inhk