hot100 合并两个有序链表(21)

本题采用双指针迭代算法又称“哑节点辅助归并法”解决两个有序单链表的合并问题。其核心本质是利用单调递增的先验条件通过双指针同步线性扫描在常数阶额外空间内将两个空间独立的拓扑序列融合成全新的全局有序链表。当前提供的源码实现了在时间复杂度 O(M N) 和额外空间复杂度 O(1) 条件下的全局最优线性检索最终走向是高效拼接所有节点并返回新链表的头节点。一、 问题本质与数据模型对于给定的两个单链表list1和list2它们在物理拓扑结构上彼此独立但在数据分布上满足相同的单调性约束均按非递减顺序排列即node.val node.next.val。若采用常规的随机构建或重新排序将破坏原有的局部有序性导致算力浪费。算法通过引入两个核心机制破除信息无序困局“哑节点Dummy Node定位模型”在合并初期由于无法预知两链表的首节点孰小直接确定新链表的头节点会引入复杂的边界判定。通过开辟一个虚拟的dummy节点作为新链表的常驻起点可以将“头节点的初始化”抽象为常规的“追加后续节点”操作从而实现控制流的归一化。“双指针线性归并机制”设置两个指针分别指向两个链表的未处理头部每次比较当前节点的数值。由于两链表局部有序当前较小者必然是全局未合并元素中的极小值将其拼接到新链表尾部能绝对保障新链表的升序物理形态。二、 算法演进对比在解决有序链表合并问题时迭代归并法在时空资源的利用效率上达到了理论极限解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷暴力重组排序法O((MN) log(MN))O(MN)将两个链表的所有节点值全部复制到数组中通过快速排序后重新物理构建一条新链表完全忽略了原链表有序的先验条件产生了高昂的排序时间损耗与外部存储空间开销递归归并法O(M N)O(M N)将问题拆解为头节点的比较剩余部分交由递归函数处理利用隐含的系统栈实现挂载递归调用会在系统栈中产生深度为 M N 的栈帧开销在超长链表下有引发栈溢出的物理风险迭代归并法当前解法O(M N)O(1)利用哑节点和双指针进行原地指针重定向单遍线性扫描即完成物理拼接指针交替推进需要严密防控链表触底时的空指针判定逻辑三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于while (list1 ! null list2 ! null)边界防护网以及后续的尾部残留挂载其内部决策分支证明如下1. 局部极小值命中分支if (list1.val list2.val)执行cur.next list1; list1 list1.next;数学证明已知两链表当前剩余部分皆为升序。若list1.val list2.val则list1.val严格小于list2集合中的所有剩余元素同时list1.val也小于或等于list1后续的所有元素。结论list1当前节点是所有未合并节点中的绝对极小值将其作为新链表的下一节点在数学上完全合规。执行步进将list1指针后移。2. 补集极小值命中分支else即list1.val list2.val执行cur.next list2; list2 list2.next;数学证明同理当list2.val小于或等于list1.val时list2.val必然小于或等于两个链表剩余集合中的任意元素。结论list2当前节点满足全局极小值条件将其拼接到cur.next并将list2指针后移。3. 残留段物理挂载cur.next (list1 ! null) ? list1 : list2;执行当while循环因其中一个链表触底变为null而终止时直接将另一非空链表挂载至cur.next。数学证明由于两个链表本身严格升序当其中一个链表被完全耗尽时另一个链表中的所有剩余节点必然都大于或等于已合并链表中的最大元素且其内部已维持升序拓扑结构。结论无需继续遍历对比直接执行 O(1) 级别的指针挂载即可保障全局有序流程提前终结。四、 算法执行状态机步进示例以输入链表list1 [1, 2, 4]list2 [1, 3, 4]为例指针状态机的演进过程如下表所示dummy初始值设为 0步骤list1当前指向list2当前指向比较状态与分支执行的核心剪枝与挂载动作新链表当前拓扑状态 (dummy.next开始)初始1 (-2-4)1 (-3-4)进入循环边界初始化cur指向dummydummy11 (-2-4)1 (-3-4)1 1 (进入 else)cur.next指向list2的 1list2后移1 (来自list2)21 (-2-4)3 (-4)1 3 (进入 if)cur.next指向list1的 1list1后移1 - 132 (-4)3 (-4)2 3 (进入 if)cur.next指向list1的 2list1后移1 - 1 - 244 (-null)3 (-4)4 3 (进入 else)cur.next指向list2的 3list2后移1 - 1 - 2 - 354 (-null)4 (-null)4 4 (进入 else)cur.next指向list2的 4list2变为null1 - 1 - 2 - 3 - 4 (来自list2)64 (-null)null循环退出判定触发残留挂载cur.next直接指向list1的 41 - 1 - 2 - 3 - 4 - 4五、 源码实现/** * 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) { // 创建独立哑节点 dummy用作新链表的固定的控制流哨兵 ListNode dummy new ListNode(0); // 初始化当前工作指针 cur指向哑节点 ListNode cur dummy; // 双指针同步推进当两个链表均未触底时执行线性比对 while (list1 ! null list2 ! null) { // 分支 1list1 节点值更小挂载 list1 并将指针后移 if (list1.val list2.val) { cur.next list1; list1 list1.next; } // 分支 2list2 节点值更小或相等挂载 list2 并将指针后移 else { cur.next list2; list2 list2.next; } // 新链表工作指针向后步进 1 位 cur cur.next; } // 边界处理将尚未遍历完毕的非空链表段直接挂载到新链表尾部 cur.next (list1 ! null) ? list1 : list2; // 返回新链表的物理真实头节点 return dummy.next; } }六、 复杂度分析1. 时间复杂度O(M N)分析设list1的长度为 Mlist2的长度为 N。在while循环的每次迭代中list1或list2的指针必定会向后推进 1 个节点同时新链表的控制指针cur也会同步推进。因此循环的最大迭代次数为 M N。当循环结束后残留段的挂载操作耗时为常数阶 O(1)。结论总的节点比较与指针重定向操作次数与两个输入链表的长度总和呈严格的线性正比关系。2. 空间复杂度O(1)分析算法在运行期间除了创建了一个用于统一控制流边界的哑节点dummy之外仅在栈内存中开辟了cur一个用于节点迭代定位的引用变量。整个重组过程是通过直接修改输入链表节点的next指针域来实现的原地In-place拼接。结论没有申请任何与输入链表规模相关的外部或临时数据结构内存空间损耗恒定为常数阶。