LeetCode如何实现两个数字相加

在LeetCode上，实现两个数字相加是一个经典的算法问题。这个问题通常以链表的形式出现，要求我们将两个表示非负整数的链表相加，并返回一个新的链表来表示它们的和。本文将详细介绍如何解决这个问题。

问题描述

给定两个非空链表，表示两个非负整数。每个链表中的节点表示一个数字位，且链表中的数字是逆序存储的。例如，链表 2 -> 4 -> 3 表示数字 342。我们的任务是将这两个链表表示的数字相加，并返回一个新的链表来表示它们的和。

解题思路

1. 初始化变量：我们需要一个变量 carry 来存储进位值，初始值为 0。同时，我们需要一个虚拟头节点 dummy 来简化链表的操作，以及一个指针 current 来跟踪当前节点。

2. 遍历链表：我们同时遍历两个链表，直到两个链表都到达末尾。在每次迭代中，我们计算当前节点的值以及进位值的和，然后更新 carry 和当前节点的值。

3. 处理进位：如果遍历结束后 carry 仍然大于 0，我们需要在结果链表的末尾添加一个新节点来存储这个进位值。

4. 返回结果：最后，我们返回虚拟头节点的下一个节点，即结果链表的头节点。

代码实现

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

复杂度分析

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

总结

通过上述方法，我们可以有效地解决LeetCode上的两个数字相加问题。关键在于正确处理进位和链表的遍历。希望本文能帮助你更好地理解这个问题，并在实际编程中应用这一算法。