EnlightenCode

两数相加 ​

这道题很有意思，它用链表来表示数字，而且是逆序存储的。也就是说，个位在链表头部，高位在尾部。比如 [2, 4, 3] 表示数字 342（不是 243）。

题目要求把两个这样的链表相加，返回一个新的链表。关键点：两个链表长度可能不同，可能有进位，最后可能还有进位（比如 99 + 1 = 100，需要多一个节点）。

最直观的想法 ​

第一次看到这题，我想到的是：先把两个链表转成数字，相加后再转回链表。

遍历链表1，从个位开始：num1 = 2 + 4*10 + 3*100 = 342。同样方法转链表2，相加，再把结果转回链表。

这个方法思路简单，但有个致命问题：数字溢出。如果链表有 100 个节点，每个节点都是 9，数字就是 10^100 - 1，JavaScript 的 Number 类型无法精确表示这么大的数。

而且，题目用链表存储就是为了避免大数问题，我们应该直接操作链表，而不是转成数字。

换个思路：模拟加法 ​

既然不能转成数字，那就直接操作链表，模拟小学做加法的过程：从个位开始，逐位相加，处理进位。

我们可以同时遍历两个链表，用两个指针分别指向当前位。计算当前位时：

  • 当前位的值 = (l1.val + l2.val + carry) % 10
  • 进位 = Math.floor((l1.val + l2.val + carry) / 10)

如果某个链表遍历完了，用 0 代替。如果最后还有进位，需要多创建一个节点。

这里有个技巧：用虚拟头节点（Dummy Head）。这样构建新链表时，不用特判第一个节点，所有节点都用 cur.next = new ListNode(...) 添加，最后返回 dummy.next 即可。

javascript
var addTwoNumbers = function(l1, l2) {
    const dummy = new ListNode(0)
    let cur = dummy
    let carry = 0
    
    // 循环条件：l1 不为空 或 l2 不为空 或 还有进位
    // 注意：即使两个链表都遍历完了，如果还有进位，需要继续
    while (l1 !== null || l2 !== null || carry !== 0) {
        const v1 = l1 ? l1.val : 0
        const v2 = l2 ? l2.val : 0
        
        const sum = v1 + v2 + carry
        carry = Math.floor(sum / 10)
        const digit = sum % 10
        
        cur.next = new ListNode(digit)
        cur = cur.next
        
        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }
    
    return dummy.next
}

为什么用虚拟头节点？ ​

虚拟头节点可以简化代码。如果没有它，我们需要特判"第一个节点"，代码会变得复杂。有了虚拟头节点，所有节点都用统一的方式添加，最后跳过虚拟头节点返回即可。

这是链表操作的一个常见技巧，在很多题目中都会用到。

边界情况 ​

有几个边界情况需要注意：

  1. 两个链表长度不同：用 0 代替已遍历完的链表的值
  2. 最后还有进位：循环条件要检查 carry !== 0
  3. 空链表：题目说非空，但代码中还是要注意 null 检查

这道题在考什么？ ​

这道题的核心是链表的操作和模拟计算过程。我们需要：

  • 同时遍历多个链表
  • 处理进位
  • 构建新链表

虚拟头节点是链表操作的一个经典技巧，可以简化代码，避免特判。

下次遇到类似题目，看到"链表"、"逐位处理"、"加法"、"进位"这些关键词，就应该想到这种思路。比如字符串相加、二进制求和这些题，虽然操作的是字符串或二进制，但思路是一样的。

记忆要点：

  • 链表操作 → 虚拟头节点
  • 逐位相加 → 模拟计算过程
  • 处理进位 → 最后可能还有进位