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. 准备当前层级的数据
            # 如果节点存在则获取值，否则为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$ 和 $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 = 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$ 和 $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 题目总结

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