LeetCode 2. 两数相加（Add Two Numbers）详细解析与多种解法
·
LeetCode 2. 两数相加详细解析
LeetCode 2. 两数相加（Add Two Numbers）详细解析
题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
codex分析
AC代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* l3 = &dummy;//取地址符
int book=0;
while(l1!=nullptr||l2!=nullptr||book!=0){
int sum=book?1:0;
if(l1!=nullptr){
sum+=l1->val;
l1=l1->next;
}
if(l2!=nullptr){
sum+=l2->val;
l2=l2->next;
}
l3->next = new ListNode(sum % 10);
l3 = l3->next;
book = sum / 10;
}
return dummy.next;
}
};
问题1：为什么要定义一个dummy指针
dummy 不是必须的，它是一个哨兵节点，用来让链表构造更方便。
在这题里，我们要不断创建新节点：cur->next = new ListNode(sum % 10);cur = cur->next;
问题是：第一个节点比较特殊。因为一开始结果链表还不存在，如果不用 dummy，你就得单独判断：
if (head == nullptr) {
head = new ListNode(sum % 10);
cur = head;
} else {
cur->next = new ListNode(sum % 10);
cur = cur->next;
}
用了 dummy 之后，就不用特殊处理第一个节点：
ListNode dummy;
ListNode* cur = &dummy;
然后每次都统一接到 cur->next 后面：
cur->next = new ListNode(sum % 10);
cur = cur->next;
最后返回：return dummy.next;
因为 dummy 本身只是临时占位，真正的结果链表是从 dummy.next 开始的。
可以这样理解：
dummy -> 2 -> 4 -> 3
^
真正答案从这里开始
所以 dummy 的作用就是：省掉“第一个节点怎么处理”的麻烦，让后续所有节点都用同一套逻辑添加。
问题2：ListNode* l3 = &dummy;的写法是什么意思 & 符号的意义
& 的核心意义就是：取变量的地址，让指针能指向它。
问题3：不用dummy，此时的代码实现，返回是l3吗
可以不用 dummy，但这时返回的一般是头指针 l3，同时还需要另一个指针负责往后接节点。
比如：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* l3 = nullptr; // 结果链表的头
ListNode* cur = nullptr; // 结果链表的尾部当前位置
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int sum = carry;
if (l1 != nullptr) {
sum += l1->val;
l1 = l1->next;
}
if (l2 != nullptr) {
sum += l2->val;
l2 = l2->next;
}
ListNode* node = new ListNode(sum % 10);
if (l3 == nullptr) {
l3 = node;
cur = node;
} else {
cur->next = node;
cur = cur->next;
}
carry = sum / 10;
}
return l3;
}
};
这里：ListNode* l3 = nullptr;
表示结果链表一开始为空。
第一次创建节点时：
l3 = node;
cur = node;
意思是：
l3 指向结果链表第一个节点
cur 也指向当前最后一个节点
之后再创建节点，就接到 cur->next：
cur->next = node;
cur = cur->next;
所以最后返回：return l3;
因为 l3 一直保存着结果链表的头节点。
不过要注意：你不能一直移动 l3。比如这样就有问题：l3 = l3->next;
如果你把 l3 往后移动了，最后它就不再指向头节点，返回会错。
所以不用 dummy 时通常要两个指针：l3 // 保存头节点，用来 returncur // 移动，用来接新节点
一句话：不用 dummy 时，返回 l3；但 l3 必须始终指向结果链表的第一个节点。
问题4：cur->next = node;cur = cur->next; 这种写法怎么理解，先定义下个指向，再赋值
总结：非赋值逻辑，而是移到下一个指针
对，你可以理解成两步：
cur->next = node;
cur = cur->next;
···
假设当前结果链表是：
```java
l3 -> 2 -> 4
^
cur
现在新建了一个节点：node -> 3
第一句：cur->next = node;
意思是：让当前尾节点 4 的 next 指向新节点 3。
链表变成：
l3 -> 2 -> 4 -> 3
^
cur
注意，这时候 cur 还指向 4。
第二句：cur = cur->next;
意思是：把 cur 往后移动一格，让它指向刚刚接上的新节点。
变成：
l3 -> 2 -> 4 -> 3
^
cur
所以这两句的逻辑是：
先把新节点接到链表尾部
再把 cur 移动到新的尾部
也可以写成：
cur->next = node;
cur = node;
因为前面刚刚执行了：cur->next = node;
所以 cur->next 和 node 指向的是同一个新节点。
不过这两句不能反过来写：
cur = cur->next;
cur->next = node;
因为原来的 cur->next 可能是 nullptr，这样 cur 会先变空，再访问 cur->next 就会出错。
题目理解（CSDN解析）
链表表示法
题目中的链表表示方式比较特殊：
- 数字的每一位存储在链表的节点中
- 逆序存储：个位在链表头部，最高位在链表尾部
- 每个节点存储一位数字（0-9）
例如：数字 342 表示为链表 2 -> 4 -> 3
问题本质
这道题的本质是模拟 竖式加法：
- 从最低位（链表头部）开始相加
- 处理进位
- 逐位计算，直到两个链表都遍历完且没有进位为止
解法一：迭代法（推荐）
算法思路
- 初始化一个哑节点（dummy node）作为结果链表的头节点前驱
- 初始化进位
carry = 0 - 同时遍历两个链表：
- 计算当前位的和：
sum = val1 + val2 + carry - 当前位的结果：
sum % 10 - 新的进位：
carry = sum // 10 - 创建新节点连接到结果链表
- 计算当前位的和：
- 如果遍历完后还有进位，需要额外创建一个节点
- 返回哑节点的下一个节点
时间复杂度
- 时间复杂度：O(max(m, n))，其中 m 和 n 分别是两个链表的长度
- 空间复杂度：O(max(m, n))，结果链表的长度最多为 max(m, n) + 1
Python 实现
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0) # 哑节点
current = 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 # 计算进位
digit = total % 10 # 计算当前位的数字
# 创建新节点
current.next = ListNode(digit)
current = current.next
# 移动指针
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
Java 实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode current = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
int digit = sum % 10;
current.next = new ListNode(digit);
current = current.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}
C++ 实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
int carry = 0;
while (l1 != nullptr || l2 != nullptr || carry != 0) {
int val1 = (l1 != nullptr) ? l1->val : 0;
int val2 = (l2 != nullptr) ? l2->val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
int digit = sum % 10;
current->next = new ListNode(digit);
current = current->next;
if (l1 != nullptr) l1 = l1->next;
if (l2 != nullptr) l2 = l2->next;
}
ListNode* result = dummy->next;
delete dummy; // 防止内存泄漏
return result;
}
};
解法二：递归法
算法思路
- 递归函数接收两个链表节点和进位作为参数
- 递归终止条件：两个链表都为空且进位为0
- 递归计算当前位的和，创建节点
- 递归计算下一位
Python 递归实现
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def add(l1, l2, carry):
# 递归终止条件
if not l1 and not l2 and carry == 0:
return None
# 计算当前位的和
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
# 创建当前节点
node = ListNode(total % 10)
# 递归计算下一个节点
next1 = l1.next if l1 else None
next2 = l2.next if l2 else None
node.next = add(next1, next2, total // 10)
return node
return add(l1, l2, 0)
算法流程图
关键点与注意事项
1. 哑节点（Dummy Node）技巧
- 使用哑节点可以简化链表操作，避免处理头节点的特殊情况
- 最后返回
dummy.next即可
2. 进位处理
- 进位的初始值为0
- 每次计算后更新进位：
carry = sum // 10 - 循环结束后如果还有进位，需要额外创建节点
3. 链表长度不一致
- 当一个链表遍历完而另一个未遍历完时，将已遍历完的链表视为0
- 使用条件判断：
val1 = l1.val if l1 else 0
4. 循环条件
- 循环条件应为
while l1 or l2 or carry，而不是while l1 and l2 - 这样可以处理链表长度不一致和最后有进位的情况
测试用例设计
基础测试
# 测试用例1：正常情况
l1 = ListNode(2, ListNode(4, ListNode(3))) # 342
l2 = ListNode(5, ListNode(6, ListNode(4))) # 465
# 预期结果：7 -> 0 -> 8 (807)
# 测试用例2：有进位
l1 = ListNode(9, ListNode(9)) # 99
l2 = ListNode(1) # 1
# 预期结果：0 -> 0 -> 1 (100)
# 测试用例3：长度不一致
l1 = ListNode(1) # 1
l2 = ListNode(9, ListNode(9)) # 99
# 预期结果：0 -> 0 -> 1 (100)
边界测试
- 两个链表都只有一个节点
- 一个链表为空（题目保证非空，但可以测试）
- 结果有多个进位：999 + 1 = 1000
- 大数相加：链表很长的情况
复杂度分析
时间复杂度
- 需要遍历两个链表的所有节点
- 时间复杂度为 O(max(m, n))，其中 m 和 n 分别是两个链表的长度
空间复杂度
- 除了结果链表外，只使用了常数级别的额外空间
- 结果链表的长度最多为 max(m, n) + 1
- 空间复杂度为 O(max(m, n))
常见错误
错误1：忘记处理最后的进位
# 错误代码
while l1 or l2:
# ... 计算
# 如果最后还有进位，会丢失
错误2：循环条件错误
# 错误代码
while l1 and l2: # 当一个链表遍历完就停止
# ...
错误3：指针移动错误
# 错误代码
l1 = l1.next # 如果 l1 可能为 None，会报错
# 应该先判断
if l1:
l1 = l1.next
扩展思考
1. 如果链表是正序存储的怎么办？
如果链表是正序存储（最高位在头部），可以：
- 先反转链表，然后使用本题解法
- 使用栈来反转顺序
- 递归计算
2. 如何优化空间复杂度？
- 可以在较长的链表上直接修改，而不是创建新链表
- 但需要注意链表不可变的情况
3. 多个链表相加
- 可以扩展为多个链表相加
- 使用类似的思路，同时遍历多个链表
总结
两数相加是链表操作中的经典题目，考察了：
- 链表的基本操作
- 数学运算中的进位处理
- 边界条件的处理能力
掌握这道题的关键在于：
- 理解逆序存储的特点
- 熟练使用哑节点简化操作
- 正确处理进位和链表长度不一致的情况
建议初学者先掌握迭代法，再尝试递归法，最后思考各种边界情况和扩展问题。
相关题目推荐
- LeetCode 445. 两数相加 II（链表正序存储）
- LeetCode 21. 合并两个有序链表
- LeetCode 206. 反转链表
- LeetCode 369. 给单链表加一
参考资料
最后更新：2024年1月
标签：链表、数学、模拟、算法
难度：中等
通过率：约 42.3%
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)