LeetCode Hot 100 2: 两数相加 (Add Two Numbers)

在这篇文章中，我们将深入探讨 LeetCode 热题“两数相加”的问题，并通过详细的案例与场景，帮助大家更好地理解和掌握这道题的解法。此题不仅考察了基础的算法和数据结构知识，也涉及到了链表的操作和数学中的进位计算。为了深入理解问题，我们将从不同的角度进行分析，提出多种解决方案，并探讨可能的优化思路。

题目描述

问题：

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

你可以假设除了数字 0 之外，这两个数字都不会以 0 开头。

示例 1：

Copy Code
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

示例 2：

Copy Code
输入：(0) + (0)
输出：0

示例 3：

Copy Code
输入：(9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9) + (9 -> 9 -> 9 -> 9)
输出：8 -> 9 -> 9 -> 9 -> 0 -> 0 -> 0 -> 1
原因：9999999 + 9999 = 10000008

解题思路

这道题目核心的解法是模拟加法运算，尤其是处理链表中每个节点所代表的数字。从个位到高位进行逐一相加，并考虑进位的问题。具体的解题思路如下：

1. 初始化：我们使用一个哑节点 dummy，它的作用是方便处理返回值（因为我们需要一个指向结果链表的指针）。然后，我们定义一个指针 p1 和 p2 分别指向两个输入链表的头节点。同时定义一个 carry 来记录每一位相加时可能产生的进位。

2. 遍历链表：从两个链表的头节点开始，逐位进行加法操作。对于每一对节点，计算它们的和，加上 carry（如果有的话），然后计算新节点的值以及新的进位。

3. 处理进位：每次加法操作后，如果和大于或等于 10，我们将进位设置为 1，否则为 0。

4. 继续遍历：当遍历完两个链表之后，仍然有进位的话，我们需要再创建一个新节点来表示进位。

5. 返回结果：最终，我们返回 dummy 节点的下一个节点，它就是结果链表的头节点。

伪代码

pythonCopy Code
def addTwoNumbers(l1, l2):
    dummy = ListNode(0)  # 哑节点
    current = dummy  # 当前节点指针
    carry = 0  # 初始化进位为 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0  # 获取 l1 当前节点的值，若 l1 已经结束则为 0
        val2 = l2.val if l2 else 0  # 获取 l2 当前节点的值，若 l2 已经结束则为 0
        sum = val1 + val2 + carry  # 计算当前位的和
        
        carry = sum // 10  # 计算进位
        current.next = ListNode(sum % 10)  # 新节点的值为当前位的和
        current = current.next  # 移动指针
        
        if l1: l1 = l1.next  # 移动 l1 指针
        if l2: l2 = l2.next  # 移动 l2 指针
    
    return dummy.next  # 返回结果链表

时间复杂度与空间复杂度

• 时间复杂度：O(max(m, n))，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的每个节点，因此时间复杂度是两个链表长度的最大值。

• 空间复杂度：O(max(m, n))，因为结果链表的最大长度可能是两个链表长度的和（若有进位的话）。

代码实现

以下是使用 Python 实现的完整代码：

pythonCopy Code
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    # 哑节点，方便操作
    dummy = ListNode(0)
    current = dummy
    carry = 0
    
    # 遍历两个链表
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0  # 获取 l1 当前节点的值
        val2 = l2.val if l2 else 0  # 获取 l2 当前节点的值
        
        sum = val1 + val2 + carry  # 计算当前位的和
        carry = sum // 10  # 计算进位
        current.next = ListNode(sum % 10)  # 创建新节点
        current = current.next  # 移动指针
        
        if l1: l1 = l1.next  # 移动 l1 指针
        if l2: l2 = l2.next  # 移动 l2 指针
    
    return dummy.next  # 返回结果链表

边界条件与优化

在实际编码过程中，我们需要考虑一些特殊的情况：

1. 链表为空：如果输入的链表为空，我们需要将其视为 0。

   例如：l1 = None 和 l2 = 0 时，返回值应为 0。

2. 进位溢出：当所有节点都处理完后，进位可能仍然存在。我们需要确保最终的进位被正确处理。

   例如：l1 = 9 -> 9 -> 9 和 l2 = 1 时，最终结果应为 0 -> 0 -> 0 -> 1。

3. 链表长度不等：输入的两个链表可能长度不同。我们在加法过程中，若某一链表已经结束，我们应该将其视为 0，继续处理另一个链表。

扩展场景

场景 1：大数相加

此题实际应用场景之一就是大数加法。在许多编程问题中，数字的大小超过了普通整数的范围。链表可以有效地存储这些大数，并且能够逐位进行加法操作。通过此题的求解，可以模拟处理大数加法的过程。

例如，在处理金融数据、计算高精度科学计算或加法问题时，可以采用链表来代表数字，然后进行相加。

场景 2：多项式加法

另一种应用场景是多项式加法。多项式中的每一项可以表示为一个节点，节点中的值表示该项的系数，节点的顺序表示多项式的次序。在多项式加法中，我们可以通过链表来表示两个多项式，并将它们按顺序相加。

例如，表达式 3x^2 + 2x + 1 和 4x^2 + 5x + 6 可以通过链表进行加法操作。

总结

“两数相加”是一道经典的 LeetCode 热题，考察了链表的操作和加法运算的模拟。通过这道题，我们不仅能熟悉链表的基本操作，还能加深对进位计算的理解，并学会处理不同长度链表的情况。在实际应用中，这种链表加法的思想可以扩展到大数相加、多项式加法等场景。

本文详细介绍了从题目理解、解法设计到代码实现的过程，希望通过多角度的分析和思考，帮助读者更好地掌握这道题的精髓，并能够灵活应用。