Leetcode 2. 两数相加

发表于
| 字数统计: 614 | 阅读时长 ≈ 2

题目描述

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

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

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

分析

这题要我们把两个链表表示的数加起来，好处是链表本身是倒序的，所以进位的话直接进到下一位就可以了。

两个链表加起来有一些情况，首先考虑链表等长的情形：

  • [1, 2, 3] + [4, 5, 6] = [5, 7, 9]，此时不存在进位直接加起来即可
  • [6, 2, 3] + [4, 5, 6] = [0, 8 ,9]，此时低位进位，但不影响总位数
  • [1, 2, 3] + [4, 5, 7] = [5, 7, 0, 1]， 这种情况最高位出现了进位导致位数增加了1

而当两个链表链表长度不一样的时候，也同样会出现这三种情况，此时需要将没有遍历完毕的链表直接连到结果中再计算进位即可。

而对于进位的计算，可以选择增加一个carry变量来记录，也可以选择在相加完毕后重头处理进位。

代码

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
26
27
28
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        node = ListNode(None)
        res = node
        # 直接计算两个链表对应值的和，先不管进位问题
        while l1 and l2:
            node.next = ListNode(l1.val + l2.val)
            l1, l2 = l1.next, l2.next
            node = node.next
        # 如果还有某个链表有剩余则加在后面
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        # 回到最初的起点
        node = res.next
        # 重新遍历整个链表，如果遇到节点值>=10的情况则将其-10，后一位+1
        while node:
            if node.val >= 10:
                node.val -= 10
                # 如果是最后一位出现进位那么在之后新建一个值为1的节点
                # [5] + [5]的这个例子一开始没有考虑到
                if not node.next:
                    node.next = ListNode(1)
                else:
                    node.next.val += 1
            node = node.next
        return res.next

执行用时 : 100 ms, 在Add Two Numbers的Python3提交中击败了92.13% 的用户

内存消耗 : 13.1 MB, 在Add Two Numbers的Python3提交中击败了92.11% 的用户