Python · 2 分钟阅读
02：两数相加
目录
题目
给你两个 非空 的链表，表示两个非负整数。它们每位数字都按照 逆序 的方式存储，
每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例
输入：l1 = [2, 4, 3] l2 = [5, 6, 4]
输出：[7, 0, 8]
解释：342 + 465 = 807
约束
- 每个链表中的节点数范围
[1, 100] 0 ≤ Node.val ≤ 9- 题目数据保证列表表示的数字不含前导零（除数字 0 本身外）
思路
链表是 逆序 存储的（个位在最前面），这刚好方便我们 从左到右模拟竖式加法：
从最低位开始相加，记录进位 carry，构造新节点。
⚠️ 不要 把链表先转成字符串再
int()求和：
- 链表的“数字”可能超过 64 位整数范围，会溢出；
- 字符串转换多了一道开销，违背题目考察链表遍历的本意。
代码实现
from __future__ import annotations
from typing import Optional
class ListNode:
"""单链表节点。"""
def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> 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
# 三个退出条件：l1、l2 任一未走完，或仍有进位
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, digit = divmod(total, 10)
cur.next = ListNode(digit)
cur = cur.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
单元测试
def build(nums: list[int]) -> Optional[ListNode]:
dummy = ListNode(0)
cur = dummy
for n in nums:
cur.next = ListNode(n)
cur = cur.next
return dummy.next
def to_list(node: Optional[ListNode]) -> list[int]:
out = []
while node:
out.append(node.val)
node = node.next
return out
if __name__ == "__main__":
s = Solution()
assert to_list(s.addTwoNumbers(build([2, 4, 3]), build([5, 6, 4]))) == [7, 0, 8]
assert to_list(s.addTwoNumbers(build([0]), build([0]))) == [0]
assert to_list(s.addTwoNumbers(build([9, 9, 9]), build([1]))) == [0, 0, 0, 1]
print("OK")
复杂度
- 时间：
O(max(N, M))，N/M分别是两个链表的长度。 - 空间：
O(max(N, M))，新建的结果链表（不算 dummy 与输入链表）。
常见变体
| 变体 | 关键改动 |
|---|---|
| 链表是 正序 存储 | 先反转再相加，再反转输出 |
| 进阶：不修改原链表（就地相加） | 复用 l1 或 l2 的节点 |
| 大数求和（不限于链表） | 使用字符串逐位相加，处理任意长度的整数 |
易错点
- 不要忘记 最后的进位（
while ... or carry）。 carry, digit = divmod(total, 10)是 Python 推荐的写法，比手算% 10清晰。- 使用 哨兵节点（dummy head）可以避免
head单独处理的 if 分支。