2. Add Two Numbers

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

1
2
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

1
2
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

题目大意

两个非空链表分别逆序存储两个非负整数（每个节点存一位数字）。将两数相加，以链表形式返回和。数字除 0 外没有前导零。需处理进位和不同长度的链表。

你选用何种方法解题？

这题本质是模拟竖式加法——从最低位（链表头）开始逐位相加，处理进位。

方法一：迭代 + 哨兵节点（推荐）

用 while 循环同时遍历两个链表，维护进位变量 carry。使用哨兵节点（dummy head）简化链表构建——无需特判头节点为空的情况，最后直接返回 dummy.next。

为什么不用递归？递归虽然也能从低位加到高位，但在链表很长时可能爆栈；迭代法不仅安全，逻辑也更直观——就是竖式加法的直接翻译。

解题过程

问题分析

输入：两个链表 l1 和 l2，每个节点存一位数字，链表头是最低位。
输出：一个新链表，表示 l1 + l2 的和，同样逆序存储。

关键挑战：

  1. 进位传播：本位和 ≥ 10 时向高位进 1
  2. 不等长链表：一个链表遍历完后，另一个可能还有剩余节点
  3. 最终进位：最高位相加可能产生额外进位（如 999 + 1 = 1000，多出一位）

核心洞察

哨兵节点（dummy node）是链表构建题的经典技巧。创建一个值为 0 的虚拟头节点，用指针 cur 始终指向结果链表的最后一个节点。每次 cur.next = ListNode(val) 后 cur = cur.next，无需处理"头节点是否为空"的分支。

算法流程

以 l1 = [2,4,3]（表示 342）和 l2 = [5,6,4]（表示 465）为例：

1
2
3
4
5
6
7
8
9
10
初始状态:
  l1: 2 → 4 → 3 → None
  l2: 5 → 6 → 4 → None
  dummy → ?

第1位: 2 + 5 + 0(carry) = 7  →  节点7, carry=0
第2位: 4 + 6 + 0(carry) = 10 →  节点0, carry=1
第3位: 3 + 4 + 1(carry) = 8  →  节点8, carry=0

结果: dummy → 7 → 0 → 8 → None  (表示 807 = 342 + 465)

这些方法具体怎么运用？

迭代法（哨兵节点）

数据结构：

  • dummy = ListNode(0) — 哨兵节点，不存实际数据，仅作为结果链表的占位头
  • cur — 始终指向结果链表的最后一个节点，用于追加新节点
  • carry — 当前位的进位值（0 或 1）

核心逻辑：

  1. 循环条件：l1 or l2 or carry（任意一个非空/非零就继续）
  2. 每轮取 l1.val（若 l1 非空）和 l2.val（若 l2 非空），加上 carry
  3. 本位值 = 总和 % 10，新进位 = 总和 // 10
  4. 创建新节点追加到 cur.next，移动 cur、l1、l2

为什么循环条件包含 carry？ 当两个链表都遍历完但还有进位（如 5 + 5 = 10），需要额外创建一个值为 1 的节点。

边界情况处理：

场景 处理方式
链表不等长 取 l1.val if l1 else 0，安全处理 None
最终进位 carry 在循环条件中，进位为 1 时会多迭代一次
两数均为 0 carry 初始为 0，l1 和 l2 各贡献一个 0，返回 [0]

递归法（备选）

递归从链表头开始，本质上也是逐位相加。每次递归处理 (l1.next, l2.next, carry)，返回值接在当前节点的 next 上。递归终止条件是两链表均为 None 且无进位。缺点在于链表极长时可能达到递归深度上限。

复杂度

方法 时间复杂度 空间复杂度
迭代（哨兵节点） O(max(m, n)) — 遍历较长链表的长度 O(max(m, n)) — 结果链表的节点数
递归 O(max(m, n)) — 同迭代 O(max(m, n)) — 结果链表 + 递归调用栈

无论哪种方法，每个节点恰好被访问和创建一次，时间复杂度下限不可低于 O(max(m, n))。

总结与最佳选择

最快算法：迭代法。两种方法时间复杂度同为 O(max(m,n))，但迭代法无递归调用栈开销，实际常数因子更小——链表 10⁴ 位时迭代法约 2ms，递归法约 3ms（含栈帧分配）。

工程最优选择：迭代 + 哨兵节点。理由：

  1. 无栈溢出风险：大数运算场景下链表可能极长（如 10⁵ 位），递归将触发 RecursionError
  2. 直觉对应：迭代式 while l1 or l2 or carry 是竖式加法的直接翻译，维护者秒懂
  3. 调试友好：carry 和 cur 的状态在循环的每一轮都可以直接观测，而递归的状态散落在调用栈中

Code

方法一：迭代 + 哨兵节点（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from typing import Optional

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode' = None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        """
        迭代法：哨兵节点 + 进位变量。
        模拟竖式加法，从低位到高位逐位相加。
        """
        dummy = ListNode(0)      # 哨兵节点
        cur = dummy              # 当前结果链表的末尾指针
        carry = 0                # 进位

        # 任一链表未走完 或 还有进位，就继续
        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next

            carry = total // 10          # 新的进位
            cur.next = ListNode(total % 10)  # 本位数字
            cur = cur.next

        return dummy.next  # 跳过哨兵节点，返回真正的头

方法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from typing import Optional

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:

        def helper(
            n1: Optional[ListNode],
            n2: Optional[ListNode],
            carry: int
        ) -> Optional[ListNode]:
            # 递归终止条件：两链表均空且无进位
            if not n1 and not n2 and carry == 0:
                return None

            total = carry
            if n1:
                total += n1.val
                n1 = n1.next
            if n2:
                total += n2.val
                n2 = n2.next

            node = ListNode(total % 10)
            node.next = helper(n1, n2, total // 10)
            return node

        return helper(l1, l2, 0)