hot100 两数相加(2)

本题采用模拟按位加法算法又称“全加器链表迭代法”解决两个大整数的逆序链表求和问题。其核心本质是利用链表逆序排列与算术竖式加法低位对齐的物理一致性通过单次线性循环与进位状态转移动态构建一个新的和链表。当前提供的源码实现了在时间复杂度 O(max(M, N)) 和空间复杂度 O(max(M, N)) 条件下的全局最优线性计算最终走向是精准输出表示两数之和的逆序链表。一、 问题本质与数据模型对于给定的两个非空单链表l1和l2每个节点存储一位十进制数字0-9。数据模型具备一个关键的先验条件逆序存储。这意味着链表的头节点即为整数的最低位个位顺着next指针向后依次为十位、百位等。这一几何拓扑结构完全契合了数学中算术加法“从低位向高位对齐计算”的本质。因此算法无需对链表进行预先反转只需从头节点同步开始向后扫描通过引入一个“进位变量carry”来维持跨节点的数位溢出状态即可完美模拟完整的竖式加法逻辑。二、 算法演进对比在解决两数相加问题时基于迭代的数据流全加器模型在时空效率上具备明显的确定性解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷数值转换法O(M N)O(1)先将两条链表分别遍历转化为标准十进制整数相加得到和后再转化为新链表当链表长度超过 64 位超过 Long.MAX_VALUE 表达范围时将发生严重的数值逆向溢出物理上不可行全加器迭代法当前解法O(max(M, N))O(max(M, N))利用一个循环条件并集将节点数值提取、进位处理、新节点生成归一化处理需要随着结果长度动态申请新节点内存空间损耗取决于最终求和结果的长度三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于while (l1 ! null || l2 ! null || carry ! 0)所构建的联合状态机控制网其内部决策及进位转移证明如下1. 循环边界判定l1 ! null || l2 ! null || carry ! 0决策证明传统的加法在两个加数都遍历完毕时即告结束。然而如果最高位产生进位例如 99 1 100在两个加数均触底为null后进位carry依然为 1。结论将carry ! 0纳入循环条件并集能够保障在最高位发生溢出进位时控制流依然能步进一次从而自动在链表末尾追加最高位的进位节点。2. 数值解耦累加分支if (l1 ! null)与if (l2 ! null)执行carry l1.val; l1 l1.next;阶梯推进。决策证明由于两个链表的长度可能不一致如一个 3 位数加一个 5 位数存在长短不对称的情况。通过独立的if条件进行隔离防护当其中一条链表提前触底时只累加非空链表的节点值。结论该结构完成了空指针防御并实现了数据流的自动零对齐若链表已空则默认其对应的数位贡献值为 0。3. 进位裂变与存储carry % 10与carry / 10执行生成当前位节点并更新进位。数学证明在十进制全加器中当前位的最大累加和为9 (来自 l1) 9 (来自 l2) 1 (前位进位) 19。结论表达式carry % 10精准提取了个位数作为当前节点的存储数值而carry / 10则保留了十位数0 或 1作为下一次循环的输入进位状态。四、 算法执行状态机步进示例以输入链表l1 [2, 4, 3]代表 342l2 [5, 6, 4]代表 465为例新链表生成及指针状态演进如下表所示dummy初始值默认步骤l1 当前指向l2 当前指向初始进位 carry累加后 carry当前位节点值 (carry % 10)更新后进位 (carry / 10)初始2 (-4-3)5 (-6-4)00-014 (-3)6 (-4)00 2 5 77023 (-null)4 (-null)00 4 6 10013nullnull11 3 4 880结束nullnull0循环退出条件触发--最终输出新链表为[7, 0, 8]代表 807。五、 源码实现/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { // 创建虚拟哑节点 dummmy用作结果链表的固定控制流哨兵 ListNode dummmy new ListNode(); // 初始化当前工作指针 cur指向哑节点 ListNode cur dummmy; // 初始化进位追踪变量 carry 为 0 int carry 0; // 核心状态机控制网当加数未完全耗尽或仍存在进位溢出时持续循环 while (l1 ! null || l2 ! null || carry ! 0) { // 若 l1 未触底将其当前位数值累加至 carry并将指针后移 if (l1 ! null) { carry l1.val; l1 l1.next; } // 若 l2 未触底将其当前位数值累加至 carry并将指针后移 if (l2 ! null) { carry l2.val; l2 l2.next; } // 取进位的个位数作为当前数位的新节点物理创建并挂载 cur.next new ListNode(carry % 10); // 新链表控制指针向后步进 1 位 cur cur.next; // 保留十位数作为下一次迭代的进位输入状态 carry / 10; } // 返回结果链表的物理真实头节点 return dummmy.next; } }六、 复杂度分析1. 时间复杂度O(max(M, N))分析设l1的长度为 Ml2的长度为 N。while循环的每一次迭代都会消耗至少一个链表中的节点只要该链表尚未触底。循环的总执行迭代次数最大等于较长链表的节点数。在极限最高位进位情况下如 99 1 100循环次数为 max(M, N) 1。结论算法整体的数值累加与节点实例化操作次数与较长链表的长度呈严格的线性正比关系。2. 空间复杂度O(max(M, N))分析算法在执行期间为了承载相加后的结果必须创建一条全新的链表。新链表的节点数最大为 max(M, N) 1即发生最高位进位时。在栈内存中仅使用了dummmy、cur、carry三个常数阶局部变量。结论除去作为题目返回值所必须开辟的新链表存储空间外该算法的纯额外辅助空间复杂度仅为常数阶 O(1)。