本文目录
1 中文题目
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请将两个数相加，并以相同形式返回一个表示和的链表。
说明：
除了数字 0 之外，其他数都不会以 0 开头。
示例 1：
- 输入： l 1 = [ 2 , 4 , 3 ] , l 2 = [ 5 , 6 , 4 ] l1 = [2,4,3], l2 = [5,6,4] l1=[2,4,3],l2=[5,6,4]
- 输出： [ 7 , 0 , 8 ] [7,0,8] [7,0,8]
- 解释： 342 + 465 = 807 342 + 465 = 807 342+465=807.
示例 2：
输入：
l
1
=
[
0
]
,
l
2
=
[
0
]
l1 = [0], l2 = [0]
l1=[0],l2=[0]
输出：
[
0
]
[0]
[0]
示例 3：
- 输入： l 1 = [ 9 , 9 , 9 , 9 , 9 , 9 , 9 ] , l 2 = [ 9 , 9 , 9 , 9 ] l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] l1=[9,9,9,9,9,9,9],l2=[9,9,9,9]
- 输出： [ 8 , 9 , 9 , 9 , 0 , 0 , 0 , 1 ] [8,9,9,9,0,0,0,1] [8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围 [ 1 , 100 ] [1, 100] [1,100] 内
- 0 ≤ N o d e . v a l ≤ 9 0 \leq Node.val \leq 9 0≤Node.val≤9
2 求解思路
2.1 基础解法： 递归解法
思路
- 每次递归处理两个链表当前节点的值相加
- 处理进位传递给下一层递归
- 递归终止条件是两个链表都为空且无进位
假设有如下输入：
l
1
=
2
→
4
→
3
l1 = 2\to4\to3
l1=2→4→3
l
2
=
5
→
6
→
4
l2 = 5\to6\to4
l2=5→6→4
递归调用的示例：
第1次递归：2+5=7, carry=0 结果：7->
第2次递归：4+6=10, carry=1 结果：7->0->
第3次递归：3+4+1=8, carry=0 结果：7->0->8
第4次递归：null+null+0=0 结果：7->0->8->null
Python代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
def recursive_add(node1, node2, carry):
# 1. 处理边界情况
if not node1 and not node2:
# 如果还有进位，创建新节点
return ListNode(carry) if carry else None
# 2. 准备当前层级的数据
# 如果节点存在则获取值，否则为0
curr_sum = carry
# 处理node1
if node1:
curr_sum += node1.val
next1 = node1.next
else:
next1 = None
# 处理node2
if node2:
curr_sum += node2.val
next2 = node2.next
else:
next2 = None
# 3. 计算当前节点值和进位
new_carry = curr_sum // 10
curr_digit = curr_sum % 10
# 4. 创建当前节点
curr_node = ListNode(curr_digit)
# 5. 递归处理下一层
curr_node.next = recursive_add(next1, next2, new_carry)
return curr_node
# 入口调用
return recursive_add(l1, l2, 0)
时空复杂度分析
N N N 和 M M M 分别是两个链表的长度
- 时间复杂度：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 需要遍历两个链表直到较长的那个结束
- 每个节点只被访问一次
- 每个节点的操作是常数时间：
- 获取节点值： O ( 1 ) O(1) O(1)
- 计算和与进位： O ( 1 ) O(1) O(1)
- 创建新节点： O ( 1 ) O(1) O(1)
- 递归调用： O ( 1 ) O(1) O(1)
- 空间复杂度：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 递归调用栈空间：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 每层递归需要保存：
- 局部变量：val1, val2, total, curr_digit, new_carry
- 当前节点指针
- 返回地址
- 递归深度等于较长链表的长度
- 每层递归需要保存：
- 新建链表空间：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 结果链表的长度最多为 m a x ( N , M ) + 1 max(N,M)+1 max(N,M)+1
- 额外的一位是因为最高位可能有进位
- 递归调用栈空间：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
2.2 最优解法：迭代法
思路
- 模拟人工加法运算过程
- 从最低位开始，逐位相加
- 处理进位传递到下一位
假设有如下输入：
l
1
=
2
→
4
→
3
l1 = 2\to4\to3
l1=2→4→3
l
2
=
5
→
6
→
4
l2 = 5\to6\to4
l2=5→6→4
迭代法的示例：
初始状态：dummy -> null
第1次循环：2+5=7 dummy -> 7
第2次循环：4+6=10 dummy -> 7 -> 0 (carry=1)
第3次循环：3+4+1=8 dummy -> 7 -> 0 -> 8
结果返回：7 -> 0 -> 8
python代码
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
# 创建哑节点作为结果链表的头部
dummy = ListNode(0)
current = dummy
carry = 0
# 当两个链表都没遍历完或还有进位时继续循环
while l1 or l2 or carry:
# 获取当前节点的值，如果节点为空则值为0
x = l1.val if l1 else 0
y = l2.val if l2 else 0
# 计算当前位的和与进位
total = x + y + 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
时空复杂度分析
N N N 和 M M M 分别是两个链表的长度
- 时间复杂度：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 遍历两个链表： O ( m a x ( N , M ) ) O(max(N,M)) O(max(N,M))
- 每个节点的操作都是
O
(
1
)
O(1)
O(1)：
- 读取节点值： O ( 1 ) O(1) O(1)
- 计算和与进位： O ( 1 ) O(1) O(1)
- 创建新节点： O ( 1 ) O(1) O(1)
- 更新指针： O ( 1 ) O(1) O(1)
- 空间复杂度：
O
(
m
a
x
(
N
,
M
)
)
O(max(N,M))
O(max(N,M))
- 结果链表： O ( m a x ( N , M ) ) O(max(N,M)) O(max(N,M))或 O ( m a x ( N , M ) + 1 ) O(max(N,M)+1) O(max(N,M)+1)
- 临时变量：O(1)
- dummy节点：1个节点空间
- current指针：1个指针空间
- carry变量：1个整数空间
- 临时计算变量(x,y,total等)：几个整数空间
相比递归法，迭代法方法直观，且不会有栈溢出的风险
3 题目总结
题目难度：中等
数据结构：链表
涉及算法：递归