两数相加
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给你两个非空的链表，表示两个非负整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。
示例 1
输入：l1 = [2,4,3], l2 = [5,6,4]（即 342 + 465）
输出：[7,0,8]（即 807）
模拟答题者思考
1. 逆序存储正好模拟竖式加法：从个位开始逐位相加。
2. 每位的和 = l1 当前位 + l2 当前位 + 进位；结果位是和对 10 取余，新进位是和整除 10。
3. 用哑结点简化头节点的处理，避免单独判断第一个节点。
4. 循环条件要包含 carry：两链表都走完但还有进位时（如 5+5）也要再建一个节点。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
dummy | ListNode* | 定义：哑结点，其 next 永远指向结果链表真正的头 维护：不变，最后返回 dummy.next 更新：不更新 |
cur | ListNode* | 定义：结果链表的尾指针 维护：始终指向已建好部分的最后一个节点 更新：每接一个新节点后 cur = cur.next |
carry | int | 定义：进位（0 或 1） 维护：等于上一位相加结果整除 10 更新：carry = 当前位和 // 10 |
落码步骤
1. 建哑结点 dummy，cur = dummy，carry = 0
2. 当 l1 或 l2 或 carry 非空时循环
3. 求和 s = carry + (l1?) + (l2?)，同时后移 l1/l2
4. carry, digit = divmod(s, 10)，新建节点接到 cur 后，cur 前移
5. 返回 dummy.next
代码实现
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode() # 哑结点，dummy.next 是结果头
cur = dummy # 结果链表尾指针
carry = 0 # 进位
while l1 or l2 or carry:
s = carry
if l1:
s += l1.val
l1 = l1.next
if l2:
s += l2.val
l2 = l2.next
carry, digit = divmod(s, 10)
cur.next = ListNode(digit)
cur = cur.next
return dummy.nextclass Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy; // 哑结点
ListNode* cur = &dummy; // 结果链表尾指针
int carry = 0; // 进位
while (l1 || l2 || carry) {
int s = carry;
if (l1) { s += l1->val; l1 = l1->next; }
if (l2) { s += l2->val; l2 = l2->next; }
carry = s / 10;
cur->next = new ListNode(s % 10);
cur = cur->next;
}
return dummy.next;
}
};
// 时间 O(max(m,n))，空间 O(max(m,n))复杂度分析
时间复杂度
O(max(m,n))
空间复杂度
O(max(m,n))
常见坑
循环条件别忘了 carry：最高位相加产生进位时还要补一个节点。
两链表长度可能不同，取值前要判空。
用哑结点避免「结果头节点」的特殊处理，最后返回 dummy.next 而不是 dummy。
必测边界 Case
Case 1：进位到新位
l1 = [5], l2 = [5] → [0,1]（5+5=10）
Case 2：长度不等
l1 = [9,9,9], l2 = [1] → [0,0,0,1]