LeetCode 2: 两数相加 - 链表数值计算
给定两个表示非负整数的非空链表，它们的数字按逆序存储，且每个节点只存储一位数字。请计算这两个数的和，并以相同格式返回结果链表。假设除了数字 0 外，这两个数均不以 0 开头。
示例
-
输入: l1 = [2->4->3], l2 = [5->6->4]
输出: [7->0->8]
解释: 342 + 465 = 807。 -
输入: l1 = [0], l2 = [0]
输出: [0] -
输入: l1 = [9->9->9->9->9->9->9], l2 = [9->9->9->9]
输出: [8->9->9->9->0->0->0->1]
解释: 9999999 + 9999 = 10009998。
约束
- 链表节点数范围：[1, 100]
- 节点值范围：[0, 9]
- 保证列表表示的数字不含前导零。
解法一：迭代模拟
由于链表以逆序存储数字，我们可以直接从链表头部开始逐位相加。在遍历过程中，同时处理进位。对于每一位，计算当前两个节点值之和加上上一位的进位。结果链表的当前节点值为该和对 10 取模，新的进位值为该和除以 10 的整数部分。
如果一个链表比另一个短，可以将其视为在末尾补零。如果在所有位都计算完毕后仍有进位，则在结果链表末尾添加一个新节点来存储这个进位。
此方法的时间复杂度为 O(max(m, n))，其中 m 和 n 是两个链表的长度。空间复杂度为 O(1)，因为我们只使用了常数额外的空间。
Python 代码实现
首先定义链表节点结构：
from typing import Optional
class ListNode:
def __init__(self, value=0, next=None):
self.val = value
self.next = next
主函数使用一个伪头节点（dummy）来简化链表构建过程。`cur` 指针用于遍历和构建新链表。
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# dummy 是伪头节点，cur 用于构建新链表
cur = dummy = ListNode()
carry = 0 # 初始化进位为0
# 循环条件：只要 l1、l2 中至少一个非空，或者有进位，就继续
while l1 or l2 or carry:
# 获取当前位的值，若链表已遍历完，则值为0
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
# 计算总和，包括进位
total_sum = val1 + val2 + carry
# 新节点的数值是总和的个位数
cur.next = ListNode(total_sum % 10)
# 更新进位，是总和的十位数
carry = total_sum // 10
# 移动 cur 指针到新创建的节点
cur = cur.next
# 移动 l1 和 l2 指针到下一个节点（如果存在）
if l1:
l1 = l1.next
if l2:
l2 = l2.next
# 返回结果链表的头节点（跳过伪头节点）
return dummy.next
示例运行
# 辅助函数用于打印链表，便于调试
def print_linked_list(head):
current = head
result = []
while current:
result.append(str(current.val))
current = current.next
print("->".join(result))
# 构造示例链表 l1: 2->4->3 (代表 342)
node3 = ListNode(3)
node4 = ListNode(4, node3)
l1_example = ListNode(2, node4)
# 构造示例链表 l2: 5->6->4 (代表 465)
node4_l2 = ListNode(4)
node6_l2 = ListNode(6, node4_l2)
l2_example = ListNode(5, node6_l2)
# 计算结果
solution = Solution()
result_list = solution.addTwoNumbers(l1_example, l2_example)
# 打印结果链表 [7->0->8]
print_linked_list(result_list) # 输出: 7->0->8
解法二：递归
这个问题也可以用递归来解决。核心逻辑与迭代类似：计算当前位的和与进位。递归函数接收两个链表的当前节点以及当前的进位值。
递归的基线条件是当两个链表节点都为空时。此时，如果存在进位，则创建一个新的节点表示该进位；否则返回 `None`。
在递归调用时，如果其中一个链表已经遍历完（节点为 `None`），则将其视为 0。为了简化代码，可以确保 `l1` 总是指向较长（或等于）的链表，如果 `l1` 为空但 `l2` 不为空，则交换它们。
递归实现的时间复杂度仍为 O(max(m, n))，但空间复杂度为 O(max(m, n))，因为递归调用栈的深度与最长链表的长度成正比。
Python 代码实现
class SolutionRecursive:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int = 0) -> Optional[ListNode]:
# 基线条件：两个链表都为空
if not l1 and not l2:
# 如果有进位，则创建一个进位节点；否则返回 None
return ListNode(carry) if carry else None
# 确保 l1 指向较长的链表，简化逻辑
if not l1:
l1, l2 = l2, l1
# 计算当前位的总和（包括进位）
current_sum = l1.val + (l2.val if l2 else 0) + carry
# 更新 l1 节点的值为当前位的个位数
l1.val = current_sum % 10
# 递归调用处理下一位
# l1.next 是下一对节点，l2.next 仅在 l2 存在时取
# carry // 10 是更新后的进位
l1.next = self.addTwoNumbers(l1.next, l2.next if l2 else None, current_sum // 10)
# 返回修改后的 l1 链表头
return l1
