题目描述

[EN | CN]

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

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

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

示例:

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

解法 1:加法竖式

题意就是一个加法竖式的计算过程:个位数加法、进位、十位数加法、进位……只是这里的数字的表示是倒序链表(数字 123 表示为链表 3->2->1)。实现跟手动计算是一样的思路,不过里面有几点要注意:

  • 用一个变量 root 来保存结果的头结点(为了最后返回),curr 保存当前结点;
  • 加完两个加数之后要注意是否还有进位,有的话再加一个结点。

假设两个数字的长度分别为 $m$、$n$,那么

  • 时间复杂度为 $O(\max(m, n))$,遍历长的那个数;
  • 空间复杂度为 $O(\max(m, n))$,保存加法结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 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:
        root = ListNode(-1)
        curr = root
        sum_ = 0

        while l1 or l2 or sum_ > 0:
            if l1:
                sum_ += l1.val
                l1 = l1.next
            if l2:
                sum_ += l2.val
                l2 = l2.next

            curr.next = ListNode(sum_ % 10)
            curr = curr.next
            sum_ = sum_ // 10

        return root.next
  • 执行用时:64 ms,在所有 Python3 提交中击败了 92.93% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.53% 的用户。