手帐 Blog

主题

复盘 · LC 2 两数相加 ​

题目 ​

题意 ​

两条非空链表分别表示两个非负整数，每位数字逆序存放（个位在头），每个节点存一位。返回它们的和，同样用逆序链表表示。

  • 例：(2 → 4 → 3) + (5 → 6 → 4) 表示 342 + 465 = 807，结果 (7 → 0 → 8)。
  • 可能出现最终进位多出一位（如 999 + 1 → 1000）。

边界：两链不等长；全是 9 进位；某一链先空但仍有 carry。

涉及算法 ​

标签一句话
模拟竖式加法同步扫两链，本位和 + 进位，建新节点
哨兵节点dummy 省掉「第一个结果节点」的特判

教程对照：13 · 链表进阶（练习清单含本题）、12 · 链表基础（哨兵习惯）。

评价我的解法 ​

先写了 index.js：给节点挂 pre 当双向链，从尾往头加——注释也写了「写到结束发现顺序反了」。根因是误读题意：题目已经把个位放在头，不需要再反转，直接从头模拟竖式即可。

我的 AC 代码（摘自 2-两数相加/index2.js）：

javascript
var addTwoNumbers = function (l1, l2) {
  let dummy = new ListNode(0);
  let cur = dummy;
  let carry = 0;
  while (l1 || l2 || carry) {
    let sum = carry;
    if (l1) {
      sum += l1.val;
      l1 = l1.next;
    }
    if (l2) {
      sum += l2.val;
      l2 = l2.next;
    }
    carry = Math.floor(sum / 10);
    cur.next = new ListNode(sum % 10);
    cur = cur.next;
  }
  return dummy.next;
};

终版干净正确（提交 1569/1569）：dummy + carry，循环条件含进位，长短链与末位进位都覆盖到了。

  • 时间 O(max(m, n))，空间 O(1) 额外（不含结果链）。
  • 优点：纠错后一次写到标准解，没有继续在双向链上打补丁。
  • 教训：链表题先盯输入约定（正序/逆序、是否带头节点），再动手；index.js 那版复杂度与心智负担都远超必要。

最佳题解 ​

与 index2.js 同构即可；写法再贴一版便于对照：

javascript
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  let carry = 0;
  while (l1 || l2 || carry) {
    const x = l1 ? l1.val : 0;
    const y = l2 ? l2.val : 0;
    const sum = x + y + carry;
    carry = Math.floor(sum / 10);
    cur.next = new ListNode(sum % 10);
    cur = cur.next;
    if (l1) l1 = l1.next;
    if (l2) l2 = l2.next;
  }
  return dummy.next;
};
  • 时间 O(max(m, n))，空间 O(1) 额外。
  • 与你的 AC 版等价；关键是「读清逆序 + 进位进循环条件」。

关联题目 ​

题为何相关
445. 两数相加 II数字正序存放，才需要栈/反转
67. 二进制求和字符串版竖式加法 + 进位
21. 合并两个有序链表双指针扫两链、哨兵拼结果

一句话带走 ​

两数相加：链表已是逆序个位在头，dummy + carry 同步扫即可——别先反转再加。