题目0002:两数相加

题目描述

给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照逆序的方式存储的,并且它们的每个节点只能存储一位数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

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

示例:

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

解答技巧

暴力法

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

图1,对两数相加方法的可视化:342+465=807,每个结点都包含一个数字,并且数字按位逆序存储。

就像你在纸上计算两个数字的和那样,我们首先从最低有效位也就是列表l1和l2的表头开始相加。由于每位数字都应当处于0…9的范围内,我们计算两个数字的和时可能会出现“溢出”。例如,5+7=12。在这种情况下,我们会将当前位的数值设置为2,并将进位carry=1带入下一次迭代。进位carry必定是0或1,这是因为两个数字相加(考虑到进位)可能出现的最大和为9+9+1=19。

伪代码如下:

将当前结点初始化为返回列表的哑结点。
将进位carry初始化为0。
将p和q分别初始化为列表l1和l2的头部。
遍历列表l1和l2直至到达它们的尾端。
- 将x设为结点p的值。如果p已经到达l1的末尾,则将其值设置为0。
- 将y设为结点q的值。如果q已经到达l2的末尾,则将其值设置为0。
- 设定sum=x+y+carry。
- 更新进位的值,carry = sum / 10。
- 创建一个数值为(sum mod10)的新结点,并将其设置为当前结点的下一个结点,然后将当前结点前进到下一个结点。
- 同时,将p和q前进到下一个结点。
检查carry = 1是否成立,如果成立,则向返回列表追加一个含有数字1的新结点。
返回哑结点的下一个结点。

请注意,我们使用哑结点来简化代码。如果没有哑结点,则必须编写额外的条件语句来初始化表头的值。

请特别注意以下情况:

测试用例	说明
`l1=[0,1],l2=[0,1,2]`	当一个列表比另一个列表长时
`l1=[],l2=[0,1]`	当一个列表为空时,即出现空列表
`l1=[9,9],l2=[1]`	求和运算最后可能出现额外的进位,这一点很容易被遗忘

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        p, q, curr = l1, l2, dummyHead
        carry = 0
        while p != None or q != None:
            x = p.val if p!=None else 0
            y = q.val if q!=None else 0
            sum_ = carry + y + x
            carry = int(sum_/10)
            curr.next = ListNode(sum_%10)
            curr = curr.next 
            if p != None: p = p.next
            if q != None: q = q.next
        if carry>0:
            curr.next = ListNode(carry)

        return dummyHead.next

复杂度分析

时间复杂度: $O(\max(m, n))$ ,假设m和n分别表示l1和l2的长度,上面的算法最多重复 $\max(m, n)$ 次。

空间复杂度: $O(\max(m, n))$ ,新列表的长度最多为 $\max(m,n)+1$ 。