LeetCode hot100——两数相加

上一篇文章我们探讨了如何合并两个有序链表。今天我们来挑战一道经典的“模拟题”。很多同学第一反应是把链表转成数字算完再转回来但在处理超大数时这种做法会彻底失效。最优雅的方式其实是回归最原始的数学方法列竖式。两数相加2. 两数相加 - 力扣LeetCode1. 生活化类比小学加法竖式想象你在纸上计算342 465。你会从个位开始相加如果满 10就向十位进 1。题目给定的链表正好是逆序存储的头节点就是个位这简直是天生为“列竖式”准备的数据结构2. 核心思路同步遍历 动态进位为了处理不等长链表和最后的进位我们采用以下策略虚拟头节点 (Dummy Node)先创建一个“地基”节点方便我们统一构建结果链表。进位变量 (carry)用来存储每一位相加后溢出的“利息”只能是 0 或 1。逻辑补零如果 $l1$ 和 $l2$ 长度不一致短的那一方在相加时我们直接看作0。循环条件只要 $l1$ 没走完、或者 $l2$ 没走完、或者最后还有一个carry没处理就不能停3. 代码实现function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { let dummy new ListNode(0); // 1. 创建虚拟头节点 let cur dummy; // 指向结果链表的当前末尾 let carry 0; // 存储进位 // 2. 核心逻辑只要还有数没加完或者还有进位 while (l1 ! null || l2 ! null || carry ! 0) { // 如果链表走完了就用 0 参与计算 const val1 l1 ? l1.val : 0; const val2 l2 ? l2.val : 0; // 计算当前位的总和 const sum val1 val2 carry; carry Math.floor(sum / 10); // 更新进位 (下一位用) const digit sum % 10; // 当前位留下的数字 // 3. 构建新节点并连接 cur.next new ListNode(digit); cur cur.next; // 4. 移动原链表指针 if (l1) l1 l1.next; if (l2) l2 l2.next; } return dummy.next; // 返回虚拟头节点的下一个即真正的答案开头 }4. 复杂度分析时间复杂度$O(\max(m, n))$。$m$ 和 $n$ 为两个链表的长度我们只需遍历一遍最长的链表。空间复杂度$O(1)$。除了存储答案的链表外我们只使用了常数个变量。5. ACM 模式写法在本地调试时我们需要配合buildList来生成测试用例。主逻辑调用const fs require(fs); function main() { try { // 模拟输入l1 [2,4,3], l2 [5,6,4] (即 342 465) const l1 buildList([2, 4, 3]); const l2 buildList([5, 6, 4]); const result addTwoNumbers(l1, l2); // 打印结果链表内容 let p result; const resArr []; while (p) { resArr.push(p.val); p p.next; } console.log(JSON.stringify(resArr)); // 输出: [7,0,8] } catch (err) { console.error(err); } } main();疑问分析1. 为什么不用数组转数字再加JavaScript 的Number.MAX_SAFE_INTEGER只能保证到 16 位左右。如果链表表示一个 100 位的数字这种方法会直接丢失精度。按位处理是应对“大数运算”的唯一王道。2. 最后的carry ! 0为什么一定要写在循环条件里考虑99 1。当两个链表都走完后最高位还会产生一个进位1。如果不把carry加入判定这个最后的1就会被丢掉导致 99 1 变成了 00。