2. 两数相加

发表于 更新于 分类于

1. 简介

链接：https://leetcode-cn.com/problems/add-two-numbers/

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

img

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

2. 题解

这里以 22 + 79 为例，我们看一下大致的流程

22+79=101，上图中，2+9 进位 1，然后 2+7+1 也会进位 1。

我们的链表逆序存储，返回的结果应为 1 → 0 → 1

我们初始化一个链表，用来存放求和结果，这里设置了两个指针 dummy 和 head，其中 head 跟随着计算结果不断指向链表尾部，dummy 一直指向初始化链表的头部，最后返回 dummy.next 就可以得到所求的链表

首先是个位相加，一开始可以看成进位 0，得到结果 11，所以个位求和后，进位为1，本位也为 1，因此 head 的下一个结点存放本位的结果 1。

上一步个位求和结果有进位 1，因此这里要求和的是 1+2+7=10，即进位为1，本位为 0。 head 的下一个结点存放本位的结果 0

上一步进行十位求和的结果中有一个进位 1，所以我们还需要继续计算下去，但是一开始求和的是两位数 22 和 79，存放这两个数值的链表取到百位的时候是 None，None 是没有属性 val，因此计算时要把 val 赋为 0。最后计算得到 1，本位为 1，进位为 0。

head 的下一个结点存放本位的结果 1，这时候 dummy 指向的是初始化的头结点，返回 dummy.next 才是所求的链表

图中的流程大致可以用文字描述为：

  • 初始化一个存放结果的链表 head，初始化进位 c 为0；
  • 如果 l1 或 l2 非空或者 c 非 0
    • 进行求和；如果 l1 非空，则取出 l1 中存放的值 v_1，若 l1 为空则设 v_1 为 0，l2 同理；
    • 求和，sum = c + v_1 + v_2，计算进位 c = sum //10，链表下一个结点存放的值为本位 head.next = ListNode(sum % 10)；
    • head 移动后链表尾部，l1 移动到下一个结点，如果 l1 为空则继续为设空，l2 同理。
  • 流程结束，返回 dummy.next 得到结果。

根据上述流程，实现的 python 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = head = ListNode()
        c = 0
        while l1 or l2 or c:
            v_1 = l1.val if l1 else 0
            v_2 = l2.val if l2 else 0
            sum = c + v_1 + v_2
            c = sum // 10
            head.next = ListNode(sum % 10)
            head = head.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next