我来给你讲解 LeetCode 第 2 题「两数相加」。

1. 题目描述

给你两个 非空 的链表，分别表示两个非负整数。链表的每个节点存储一个数字，这些数字是 逆序 存储的（即个位在链表头部）。
请你将这两个数相加，并以相同形式返回一个表示和的链表。

示例
输入：l1 = [2,4,3]（表示整数 342），l2 = [5,6,4]（表示整数 465）
输出：[7,0,8]（表示 342 + 465 = 807，逆序存储为 7 → 0 → 8）

2. 思路分析

因为数字是逆序存储的，所以链表的头是个位，依次是十位、百位等。
这样我们可以直接从头开始逐位相加，并处理进位。

步骤：

1. 初始化一个哑结点（dummy node）作为结果链表的头部前驱，方便操作。
2. 用一个变量 carry 记录进位（初始为 0）。
3. 同时遍历两个链表，直到两个链表都到末尾且没有进位为止：
   • 取 l1 当前节点的值（如果 l1 已空则为 0）
   • 取 l2 当前节点的值（如果 l2 已空则为 0）
   • 计算当前位的和：sum = val1 + val2 + carry
   • 当前位的结果为 sum % 10，新的进位为 sum // 10
   • 将当前位结果作为新节点接到结果链表
   • 移动 l1、l2 指针（如果还有节点）
4. 返回 dummy.next。

3. 详细步骤举例

以 l1 = [2,4,3]，l2 = [5,6,4] 为例：

初始：
dummy → null
carry = 0
p = dummy

第 1 位（个位）：
l1.val = 2, l2.val = 5
sum = 2 + 5 + 0 = 7
carry = 0
新节点 7，链表变为 dummy → 7
移动 l1, l2 到下一个节点

第 2 位（十位）：
l1.val = 4, l2.val = 6
sum = 4 + 6 + 0 = 10
当前位 = 10 % 10 = 0，carry = 1
新节点 0，链表变为 dummy → 7 → 0
移动 l1, l2 到下一个节点

第 3 位（百位）：
l1.val = 3, l2.val = 4
sum = 3 + 4 + 1 = 8
当前位 = 8，carry = 0
新节点 8，链表变为 dummy → 7 → 0 → 8
移动 l1, l2 到末尾（null）

检查进位：carry = 0，结束。

结果链表为 7 → 0 → 8，表示数字 807。

4. 边界情况考虑

• 两个链表长度不同：比如 l1 = [9,9,9]，l2 = [9]
  短的在遍历完后用 0 补位。
• 最后还有进位：比如 l1 = [5]，l2 = [5]
  结果应为 [0,1]，需要额外创建一个节点存储进位 1。

5. 代码框架（Python）

def addTwoNumbers(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        total = val1 + val2 + carry
        carry = total // 10
        curr.next = ListNode(total % 10)
        curr = curr.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    
    return dummy.next

6. 复杂度分析

• 时间复杂度：O(max(m, n))，m 和 n 分别是两个链表的长度。
• 空间复杂度：O(max(m, n))，结果链表的长度最多为 max(m, n) + 1。