LeetCode中两数相加的示例分析

在LeetCode的众多算法题中，”两数相加”（Add Two Numbers）是一个经典的链表操作问题。这个问题不仅考察了链表的基本操作，还涉及到了进位处理等细节。本文将通过一个具体的示例，详细分析如何解决这个问题。

问题描述

给定两个非空的链表，表示两个非负的整数。每个链表中的每个节点存储一个数字，且这些数字是逆序存储的。例如，链表 2 -> 4 -> 3 表示整数 342。要求将这两个数相加，并以相同的形式返回一个新的链表。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
解释：342 + 465 = 807

解题思路

要解决这个问题，我们需要模拟两个数的加法过程。具体步骤如下：

1. 初始化：创建一个新的链表来存储结果，并初始化一个进位变量 carry 为 0。
2. 遍历链表：同时遍历两个链表，将对应节点的值相加，并加上进位 carry。
3. 处理进位：如果相加的结果大于等于 10，则需要进位，将 carry 设置为 1，并将当前节点的值设置为 sum % 10。
4. 处理链表长度不一致的情况：如果两个链表的长度不一致，较短的链表在遍历结束后，剩余的节点值需要与 carry 相加。
5. 处理最后的进位：如果遍历结束后，carry 仍然为 1，则需要在新链表的末尾添加一个值为 1 的节点。
6. 返回结果：返回新链表的头节点。

代码实现

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

def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy
    carry = 0
    
    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0
        
        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next
        
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next
    
    return dummy.next

示例分析

让我们通过一个具体的示例来详细分析代码的执行过程。

输入：

l1: 2 -> 4 -> 3
l2: 5 -> 6 -> 4

执行过程：

1. 初始化：

   • dummy 节点为 0，current 指向 dummy，carry 为 0。

2. 第一次循环：

   • val1 = 2，val2 = 5，total = 2 + 5 + 0 = 7。
   • carry = 7 // 10 = 0，current.next = ListNode(7 % 10) = ListNode(7)。
   • current 移动到 ListNode(7)。
   • l1 和 l2 分别移动到下一个节点。

3. 第二次循环：

   • val1 = 4，val2 = 6，total = 4 + 6 + 0 = 10。
   • carry = 10 // 10 = 1，current.next = ListNode(10 % 10) = ListNode(0)。
   • current 移动到 ListNode(0)。
   • l1 和 l2 分别移动到下一个节点。

4. 第三次循环：

   • val1 = 3，val2 = 4，total = 3 + 4 + 1 = 8。
   • carry = 8 // 10 = 0，current.next = ListNode(8 % 10) = ListNode(8)。
   • current 移动到 ListNode(8)。
   • l1 和 l2 都为 None，循环结束。

5. 返回结果：

   • dummy.next 指向 7 -> 0 -> 8，即结果为 7 -> 0 -> 8。

输出：

7 -> 0 -> 8

复杂度分析

• 时间复杂度：O(max(m, n))，其中 m 和 n 分别是两个链表的长度。我们需要遍历两个链表的每一个节点。
• 空间复杂度：O(max(m, n))，新链表的长度最多为 max(m, n) + 1。

总结

通过这个示例分析，我们可以看到，”两数相加”问题的关键在于模拟加法过程，并正确处理进位和链表长度不一致的情况。通过使用一个虚拟头节点 dummy，我们可以简化链表的操作，避免处理头节点的特殊情况。希望本文的分析能够帮助你更好地理解这个问题，并在LeetCode的练习中取得更好的成绩。