2. 两数相加 (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/add-two-numbers/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
示例：
- 输入：l1 = [2,4,3], l2 = [5,6,4]
- 输出：[7,0,8]
- 解释：342 + 465 = 807
题目详细分析
- 数据范围： 两个链表的节点数分别在 [1, 100] 范围内，节点值在 [0, 9] 范围内
- 输入特征： 数字按逆序存储，即链表头节点是个位，下一个是十位，依次类推
- 核心约束： 不能直接将链表转换为整数再相加，因为链表长度可达 100 位，远超 64 位整数的表示范围
- 隐藏条件： 逆序存储实际上方便了我们模拟竖式加法——从个位开始逐位相加，与链表遍历方向一致
- 边界条件： 两个链表长度不同、相加后有进位（特别是最后一次进位需要额外创建节点）
小白版直白理解
就像我们小学做加法竖式一样：把两个数字从个位开始对齐，逐位相加，满十进一。
这道题的巧妙之处在于，链表已经是「反着」存储的（个位在头节点），所以遍历链表的顺序正好就是从个位到最高位的顺序，和竖式加法完全一致。
唯一需要注意的是两个数字的位数可能不同——位数短的那个，高位就当 0 处理。
解题思路
思路一：模拟竖式加法 + 虚拟头节点（推荐）
为什么这样想： 逆序存储意味着我们可以直接同步遍历两个链表，模拟竖式加法的逐位相加过程。关键是用一个变量 carry 记录进位。
关键洞察： 循环条件用 while l1 or l2 or carry 可以统一处理三个情况：链表还有节点、链表遍历完了但还有进位。当某个链表遍历完时，对应的 val 视为 0。
def addTwoNumbers(l1, l2):
"""模拟竖式加法"""
dummy = ListNode(0) # 虚拟头节点
cur = dummy
carry = 0 # 进位
while l1 or l2 or carry:
# 取当前位的值，链表为空时取 0
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10 # 新的进位
cur.next = ListNode(total % 10) # 当前位的值
cur = cur.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next思路二：递归法
思路讲解： 递归处理每一对节点。每次计算 l1.val + l2.val + carry 的当前位和进位，当前位创建新节点，进位传给下一层递归。
def addTwoNumbers(l1, l2, carry=0):
"""递归法"""
if not l1 and not l2 and not carry:
return None
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
node = ListNode(total % 10)
node.next = addTwoNumbers(
l1.next if l1 else None,
l2.next if l2 else None,
total // 10
)
return node思路三：补零使两链表等长
思路讲解： 先遍历较短的链表，在其末尾补 0 节点使其与长链表等长，然后同步遍历相加。这样写循环时不需要每次都判断 None，但会修改原链表结构。
def addTwoNumbers(l1, l2):
"""补零法"""
# 先计算长度
def get_len(node):
length = 0
while node:
length += 1
node = node.next
return length
len1, len2 = get_len(l1), get_len(l2)
# 给短的补零
dummy_short = ListNode(0)
cur = dummy_short
if len1 < len2:
for _ in range(len2 - len1):
cur.next = ListNode(0)
cur = cur.next
cur.next = l1
l1 = dummy_short.next
else:
for _ in range(len1 - len2):
cur.next = ListNode(0)
cur = cur.next
cur.next = l2
l2 = dummy_short.next
# 同步遍历相加
dummy = ListNode(0)
cur = dummy
carry = 0
while l1:
total = l1.val + l2.val + carry
carry = total // 10
cur.next = ListNode(total % 10)
cur = cur.next
l1 = l1.next
l2 = l2.next
if carry:
cur.next = ListNode(carry)
return dummy.next易错点
- 最后一位进位： 当两个链表都遍历完后，如果 carry 仍为 1，需要额外创建一个值为 1 的节点
- 循环条件： 用
while l1 or l2 or carry而不是while l1 and l2，前者能处理长度不等的进位情况 - 取 val 时判空：
l1.val if l1 else 0而不是直接l1.val，因为 l1 可能已经为空 - 链表前进： 只有当前节点不为空时才移动指针，否则会在 None 上调用 .next
- 虚拟头节点返回： 返回
dummy.next而不是cur
框架提炼
链表竖式加法模板： 适用于两个链表表示的数字做加法（以及其他逐位运算如减法、乘法）。
def add_two_numbers(l1, l2):
dummy = ListNode(0)
cur = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
total = v1 + v2 + carry
carry = total // 10
cur.next = ListNode(total % 10)
cur = cur.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next推广： 这个模板可以用于「正序存储」的加法（445. 两数相加 II），只需先反转链表再用此模板。
关联题目
- 21-合并两个有序链表 — 同步遍历两个链表，类似的「双路遍历」模式
- 445-两数相加II — 正序存储的两数相加，需要先反转链表再应用本题模板
- 43-字符串相乘 — 大数相乘（非链表版），核心也是模拟竖式运算