企业服务内容怎么写_123网址大全_seo快排优化_百度搜索词排名

1 中文题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请将两个数相加，并以相同形式返回一个表示和的链表。

说明：
除了数字 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]$

提示：

• 每个链表中的节点数在范围 $[1,100]$ 内
• $0\le Node.val\le 9$

---

2 求解思路

2.1 基础解法： 递归解法

思路

• 每次递归处理两个链表当前节点的值相加
• 处理进位传递给下一层递归
• 递归终止条件是两个链表都为空且无进位

假设有如下输入：

$l1=2\to 4\to 3$
$l2=5\to 6\to 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. 准备当前层级的数据# 如果节点存在则获取值，否则为0curr_sum = carry# 处理node1if node1:curr_sum += node1.valnext1 = node1.nextelse:next1 = None# 处理node2if node2:curr_sum += node2.valnext2 = node2.nextelse:next2 = None# 3. 计算当前节点值和进位new_carry = curr_sum // 10curr_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$ 和 $M$ 分别是两个链表的长度

• 时间复杂度：$O(max(N,M))$
  • 需要遍历两个链表直到较长的那个结束
  • 每个节点只被访问一次
  • 每个节点的操作是常数时间：
    • 获取节点值：$O(1)$
    • 计算和与进位：$O(1)$
    • 创建新节点：$O(1)$
    • 递归调用：$O(1)$
• 空间复杂度：$O(max(N,M))$
  • 递归调用栈空间：$O(max(N,M))$
    • 每层递归需要保存：
      • 局部变量：val1, val2, total, curr_digit, new_carry
      • 当前节点指针
      • 返回地址
    • 递归深度等于较长链表的长度
  • 新建链表空间：$O(max(N,M))$
    • 结果链表的长度最多为$max(N,M)+1$
    • 额外的一位是因为最高位可能有进位

---

2.2 最优解法：迭代法

思路

• 模拟人工加法运算过程
• 从最低位开始，逐位相加
• 处理进位传递到下一位

假设有如下输入：

$l1=2\to 4\to 3$
$l2=5\to 6\to 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 = dummycarry = 0# 当两个链表都没遍历完或还有进位时继续循环while l1 or l2 or carry:# 获取当前节点的值，如果节点为空则值为0x = l1.val if l1 else 0y = l2.val if l2 else 0# 计算当前位的和与进位total = x + y + carrycarry = total // 10    # 获取进位digit = total % 10     # 获取当前位# 创建新节点并连接到结果链表current.next = ListNode(digit)current = current.next# 移动指针到下一个节点if l1: l1 = l1.nextif l2: l2 = l2.nextreturn dummy.next

时空复杂度分析

$N$ 和 $M$ 分别是两个链表的长度

• 时间复杂度：$O(max(N,M))$
  • 遍历两个链表：$O(max(N,M))$
  • 每个节点的操作都是$O(1)$：
    • 读取节点值：$O(1)$
    • 计算和与进位：$O(1)$
    • 创建新节点：$O(1)$
    • 更新指针：$O(1)$
• 空间复杂度：$O(max(N,M))$
  • 结果链表：$O(max(N,M))$或$O(max(N,M)+1)$
  • 临时变量：O(1)
    • dummy节点：1个节点空间
    • current指针：1个指针空间
    • carry变量：1个整数空间
    • 临时计算变量(x,y,total等)：几个整数空间

相比递归法，迭代法方法直观，且不会有栈溢出的风险

---

3 题目总结

题目难度：中等
数据结构：链表
涉及算法：递归