链表两数相加深度解析【进位】【边界条件】【迭代】【递归】

链表两数相加深度解析（LeetCode 2/445）

目录

• 题目描述与背景
• 核心问题分析
• 方法一：递归解法
• 方法二：迭代解法
• 递归到迭代的思维转换
• 相关题型：两数相加II
• 代码实现（多语言）
• 算法复杂度分析
• 常见错误与边界分析
• 思想拓展与应用
• 总结

---

题目描述与背景

LeetCode 2: 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

示例：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

LeetCode 445: 两数相加II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

示例：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

---

核心问题分析

问题本质

链表加法本质上就是模拟人工竖式计算的过程：

1. 从最低位开始，逐位相加
2. 处理进位问题
3. 构建结果链表

关键挑战

1. 进位处理：当前位相加可能产生进位，需要传递到下一位
2. 链表长度不同：两个链表可能长度不同，需要处理空节点
3. 最终进位：最高位可能还有进位，需要额外处理

算法框架

初始化进位 carry = 0
while (l1 不为空 OR l2 不为空 OR carry > 0):当前位和 = l1.val + l2.val + carry当前位值 = 当前位和 % 10进位 = 当前位和 / 10创建新节点存储当前位值移动到下一位

---

方法一：递归解法

递归思想

将问题分解为：当前位计算 + 剩余位递归计算

递归终止条件

• l1 == null && l2 == null && carry == 0

递归逻辑

• 计算当前位的和：sum = l1.val + l2.val + carry
• 当前位值：sum % 10
• 进位值：sum / 10
• 递归处理下一位

代码实现

写法一：创建新节点

class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:# 递归边界：两个链表都为空且无进位if l1 is None and l2 is None and carry == 0:return None# 计算当前位的和s = carryif l1:s += l1.vall1 = l1.nextif l2:s += l2.vall2 = l2.next# 创建当前节点，递归处理下一位return ListNode(s % 10, self.addTwoNumbers(l1, l2, s // 10))

写法二：原地修改（优化技巧）

class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry=0) -> Optional[ListNode]:# 递归边界if l1 is None and l2 is None:return ListNode(carry) if carry else None# 优化技巧：保证l1非空，简化代码逻辑if l1 is None:l1, l2 = l2, l1# 计算当前位s = carry + l1.val + (l2.val if l2 else 0)l1.val = s % 10  # 直接修改原链表# 递归处理下一位l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, s // 10)return l1

递归的优势与劣势

优势：

• 代码简洁，逻辑清晰
• 天然符合问题的递归结构
• 易于理解和实现

劣势：

• 空间复杂度O(n)，需要递归栈空间
• 对于超长链表可能导致栈溢出
• 性能相对较差

---

方法二：迭代解法

迭代思想

使用双指针同步遍历两个链表，模拟竖式计算过程。

核心技巧：哨兵节点

• 创建一个虚拟头节点（哨兵节点）
• 简化链表操作，避免头节点特殊处理
• 最终返回dummy.next

代码实现

class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:cur = dummy = ListNode()  # 哨兵节点carry = 0  # 进位# 只要有一个链表不为空，或者还有进位，就继续迭代while l1 or l2 or carry:# 累加当前位的值if l1:carry += l1.vall1 = l1.nextif l2:carry += l2.vall2 = l2.next# 创建新节点存储当前位值cur.next = ListNode(carry % 10)carry //= 10  # 更新进位cur = cur.next  # 移动到下一个节点return dummy.next  # 返回真正的头节点

迭代的优势

• 空间复杂度O(1)：只使用常数额外空间
• 性能更优：避免了递归调用开销
• 更安全：不会栈溢出
• 工业级代码：实际项目中更常用

---

递归到迭代的思维转换

思维转换过程

1. 递归思维

当前问题 = 当前位计算 + 子问题(剩余位)

2. 迭代思维

使用循环 + 状态变量 模拟递归过程
- 循环条件：模拟递归终止条件
- 状态变量：carry（模拟递归参数）
- 指针移动：模拟递归调用

转换技巧

1. 递归终止条件 → 循环条件

# 递归终止条件
if l1 is None and l2 is None and carry == 0:return None# 转换为循环条件
while l1 or l2 or carry:

2. 递归参数 → 状态变量

# 递归参数
def addTwoNumbers(l1, l2, carry=0)# 转换为状态变量
carry = 0  # 在循环中维护

3. 递归调用 → 指针移动

# 递归调用
return ListNode(val, addTwoNumbers(l1.next, l2.next, new_carry))# 转换为指针移动
cur.next = ListNode(val)
cur = cur.next
l1 = l1.next
l2 = l2.next

---

相关题型：两数相加II

问题特点

• 数字是正序存储（最高位在链表开头）
• 不能直接使用LeetCode 2的解法

解题思路

方法一：反转链表

1. 反转两个输入链表
2. 使用LeetCode 2的解法相加
3. 反转结果链表

class Solution:def reverseList(self, head):"""反转链表"""pre = Nonecur = headwhile cur:nxt = cur.nextcur.next = prepre = curcur = nxtreturn predef addTwo(self, l1, l2):"""LeetCode 2的解法"""cur = dummy = ListNode()carry = 0while l1 or l2 or carry:if l1: carry += l1.vall1 = l1.nextif l2: carry += l2.vall2 = l2.nextcur.next = ListNode(carry % 10)carry //= 10cur = cur.nextreturn dummy.nextdef addTwoNumbers(self, l1, l2):# 反转链表l1 = self.reverseList(l1)l2 = self.reverseList(l2)# 相加l3 = self.addTwo(l1, l2)# 反转结果return self.reverseList(l3)

方法二：栈（进阶解法）

1. 将两个链表的值分别压入栈
2. 从栈顶开始相加（相当于从最低位开始）
3. 构建结果链表

class Solution:def addTwoNumbers(self, l1, l2):# 使用栈存储链表值stack1, stack2 = [], []# 压栈while l1:stack1.append(l1.val)l1 = l1.nextwhile l2:stack2.append(l2.val)l2 = l2.next# 从栈顶开始相加carry = 0result = Nonewhile stack1 or stack2 or carry:val1 = stack1.pop() if stack1 else 0val2 = stack2.pop() if stack2 else 0total = val1 + val2 + carry# 头插法构建结果链表new_node = ListNode(total % 10)new_node.next = resultresult = new_nodecarry = total // 10return result

---

代码实现（多语言）

Python

# 迭代解法（推荐）
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:cur = dummy = ListNode()carry = 0while l1 or l2 or carry:if l1:carry += l1.vall1 = l1.nextif l2:carry += l2.vall2 = l2.nextcur.next = ListNode(carry % 10)carry //= 10cur = cur.nextreturn dummy.next

C++

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* dummy = new ListNode(0);ListNode* cur = dummy;int carry = 0;while (l1 || l2 || carry) {if (l1) {carry += l1->val;l1 = l1->next;}if (l2) {carry += l2->val;l2 = l2->next;}cur->next = new ListNode(carry % 10);carry /= 10;cur = cur->next;}return dummy->next;}
};

---

算法复杂度分析

时间复杂度

• O(max(M, N))：其中M和N是两个链表的长度
• 每个节点最多被访问一次
• 进位处理是常数时间操作

空间复杂度

• 递归解法：O(max(M, N)) - 递归栈空间
• 迭代解法：O(1) - 只使用常数额外空间（返回值不计入）

性能对比

方法	时间复杂度	空间复杂度	适用场景
递归	O(max(M,N))	O(max(M,N))	代码简洁，链表较短
迭代	O(max(M,N))	O(1)	生产环境，链表较长

---

常见错误与边界分析

常见错误

1. 忘记处理最终进位

# 错误：没有处理最后的进位
while l1 or l2:  # 缺少 carry 条件# ...# 正确：包含进位条件
while l1 or l2 or carry:# ...

2. 链表指针移动错误

# 错误：在累加前就移动指针
carry += l1.val
l1 = l1.next  # 应该在累加后移动# 正确：先累加，再移动
if l1:carry += l1.vall1 = l1.next

3. 返回错误节点

# 错误：返回哨兵节点
return dummy# 正确：返回哨兵节点的下一个节点
return dummy.next

边界情况

1. 空链表：l1或l2为空
2. 长度不同：一个链表比另一个长
3. 最终进位：最高位产生进位
4. 全零：两个链表都表示0

---

思想拓展与应用

1. 大数运算

链表加法是大数运算的基础，可以扩展到：

• 大数乘法
• 大数除法
• 大数幂运算

2. 进制转换

可以扩展到不同进制的加法：

def addTwoNumbersBase(self, l1, l2, base=10):# 只需要修改进位计算carry //= base  # 而不是 carry //= 10cur.next = ListNode(carry % base)

3. 多项式加法

链表可以表示多项式，每个节点存储系数和指数：

class PolyNode:def __init__(self, coefficient, power):self.coefficient = coefficientself.power = powerself.next = None

4. 字符串加法

类似思想可以应用到字符串加法：

def addStrings(self, num1: str, num2: str) -> str:# 从右到左逐位相加，处理进位# 与链表加法思想完全一致

5. 相关题型

• LeetCode 67: 二进制求和
• LeetCode 415: 字符串相加
• LeetCode 989: 数组形式的整数加法
• LeetCode 369: 给单链表加一

---

递归与迭代的深度对比

递归的本质

递归是分治思想的体现：

• 将大问题分解为相同的小问题
• 通过函数调用栈保存状态
• 天然符合问题的递归结构

迭代的本质

迭代是状态机的体现：

• 使用循环和状态变量
• 显式管理状态转换
• 更接近计算机的执行方式

选择建议

• 学习阶段：先掌握递归，理解问题本质
• 面试阶段：优先展示迭代解法
• 生产环境：使用迭代解法，性能更好

---

总结

核心要点

1. 进位处理：是链表加法的核心，需要仔细处理
2. 哨兵节点：简化链表操作，避免头节点特殊处理
3. 递归到迭代：掌握思维转换，提高代码质量
4. 边界处理：考虑各种边界情况，写出健壮的代码

算法思想

• 模拟人工计算：将竖式计算过程用代码实现
• 双指针技巧：同步遍历两个链表
• 状态管理：通过变量维护进位状态

应用价值

• 大数运算基础：为更复杂的数值计算提供基础
• 链表操作经典：掌握链表的基本操作技巧
• 递归迭代转换：理解两种编程范式的转换

学习建议

1. 先理解递归解法，掌握问题本质
2. 练习递归到迭代的转换
3. 掌握哨兵节点等链表技巧
4. 扩展到相关题型，形成知识体系

链表两数相加是链表操作的经典题目，掌握其解法对于理解链表操作、递归迭代转换、以及大数运算都有重要意义。通过深入理解这道题，可以为后续学习更复杂的链表问题打下坚实基础。