Leetcode2-两数相加

---

---

题目

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

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

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

让我们来分析一下题目：

已知：两个整数以两个非空的链表表示（非负、逆序）

目的：求两个整数的和

要求：和以链表形式表示（每个节点一位数）

---

一、示例

示例1

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

分析：将两个整数342和456以链表形式表示，并且链表中的数是逆序的，然后将每个对应的数字相加，如2+5=7,4+6=10，但是注意要求每个节点一位数字，所以这里不能写10，因为“10”是两位数字，所以向后进一位，3+4+1=8，其中+1为进位。

示例2

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

示例3

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

解析

迭代法

迭代法的思路比较节点就是将两个链表从多到右对应数字相加，如果大于等于10，则将数位数字向后进位。

在解决问题之前我们先了解两个符号：“/” 和 “%”

“/” ：两个数相除时能被整除的倍数，例如12/10=1

“%” ：两个数相处时的余数，例如12/10=2

假如有999和99两个整数，将其转化为链表，对位位置求和，其中9+9=18，将十位向后进位留下个位8,9+9+1=19同理将十位进位留下9,9+1=10将十位进位留下0，最后为进位1，所以最后结果为1098。

伪代码

        func(l1, l2) ——> ListNode:
            total = 0
            next1 = 0
            result = ListNode()
            cur = result
            while (l1 != null and l2 != null):
                total = l1.val + l2.val + next1
                cur.next = ListNode(total%10)
                next1 = total / 10
                l1 = l1.next
                l2 = l2.next
                cur = cur.next

            while l1 != null:
                total = l1.val + next1
                cur.next = ListNode(total%10)
                next1 = total / 10
                l1 = l1.next
                cur = cur.next
            
            while l2 != null:
                total = l2.val + next1
                cur.next = ListNode(total%10)
                next1 = total / 10
                l2 = l2.next
                cur = cur.next

            if next1 != 0:
                cur.next = ListNode(next1)
            return result.next
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
29
30

首先创建一个函数，输入的时l1、l2两个链表，返回的是一个新链表

 func(l1, l2) ——> ListNode:
1

初始化两个参数，total为两个节点的加和值，next1为进位值有进位时为1没有进位时为0，result为创建的新链表，cur为result中当前列表的最后节点

            total = 0
            next1 = 0
            result = ListNode()
            cur = result
1
2
3
4

首先使用while循环从前到后将两个链表的数字相加，循环的条件为两个链表都有元素（l1 != null and l2 != null）

while (l1 != null and l2 != null):
1

其中求和是将当前l1链表的节点值 l1.val 和当前l2链表的节点值 l2.val 与 进位值 next1 相加

 total = l1.val + l2.val + next1
1

将相加的结果中个位数添加到新节点cur.next，而十位数添加到进位值next1

cur.next = ListNode(total%10)
next1 = total / 10
1
2

然后将链表l1、 l2 和 结果的节点指针cur 分别指向下一个节点进行循环

l1 = l1.next
l2 = l2.next
cur = cur.next
1
2
3

如果当l2 链表中数字全部遍历完，而l1中还有数字时，将l1当前节点值加上进位值（注意这里的进位值可能是0也可能时1，具体情况要看上一节点的是否有进位），然后将结果中个位数添加到新节点cur.next，而十位数添加到进位值next1，最后将链表l1 结果的节点指针cur 分别指向下一个节点进行循环，指导l1 中没有数字推出循环

while l1 != null:
	total = l1.val + next1
	cur.next = ListNode(total%10)
	next1 = total / 10
	l1 = l1.next
	cur = cur.next
1
2
3
4
5
6

如果当l1 链表中数字全部遍历完，而l2中还有数字时，同理如上

 while l2 != null:
	total = l2.val + next1
	cur.next = ListNode(total%10)
	next1 = total / 10
	l2 = l2.next
	cur = cur.next
1
2
3
4
5
6

如果两个链表全部遍历完了，则看最后一个节点的和中是否有进位值，即next1为0还是为1，如果next1为1则继续创建一个节点，节点值为1，如果next1为0则退出

if next1 != 0:
	cur.next = ListNode(next1)
return result.next
1
2
3

python 代码

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        total = 0
        next1 = 0
        result = ListNode()
        cur = result
        while (l1 != None and l2 != None):
            total = l1.val + l2.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l1 = l1.next
            l2 = l2.next
        
        while l1 != None:
            total = l1.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l1 = l1.next
        
        while l2 != None:
            total = l2.val + next1
            cur.next = ListNode(total % 10)
            next1 = total // 10
            cur = cur.next
            l2 = l2.next
        
        if next1 != 0:
            cur.next = ListNode(next1)
        
        return result.next
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
29
30
31
32

递归法

递归法的思想如下，l1、l2为两个链表，res为结果输出的链表，next为是否有进位。首先将两个链表从上到下依次将对位未知出的数字进行相加，将相加结果的个位填入res节点中，将进位值填入next中，在进行下一次递归时，将next加到l1链表的下一节点中，如图中节点9加上进位值变成了10，然后在与l2中的第二个节点9相加，个位填入res中十位填入进位值next中，依次进行，当链表中节点不足时用0补充。

伪代码

        func(l1, l2) ——>ListNode:
            total = l1.val + l2.val
            next1 = total / 10
            res = ListNode(total%10)
            if (l1.nest != null or l2.nest != null or next1 != null):
                if (l1.next != null):
                    l1 = l1.next
                else:
                    l1.ListNode(0)

                if (l2.next != null):
                    l2 = l2.next
                else:
                    l2 = ListNode(0)
                
                l1.val = l1.val + next1
                res.next = func(l1, l2)
            return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

代码前面部分与迭代法类似不在陈述，我么直接看if判断，如果l1、 l2和 next1 都不为空，则说明链表中还有元素，如果l1中有元素，则将指针指向下一节点，否则创建0节点

if (l1.next != null):
	l1 = l1.next
else:
	l1.ListNode(0)
1
2
3
4

同理，如果l2中有元素，则将指针指向下一节点，否则创建0节点

if (l2.next != null):
	l2 = l2.next
else:
	l2.ListNode(0)
1
2
3
4

然后，将进位值与l1当前节点相加，将当前l1、l2的节点重新输入函数进行递归

l1.val = l1.val + next1
                res.next = func(l1, l2)
1
2

python 代码

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        total = l1.val + l2.val
        next1 = total // 10
        res = ListNode(total % 10)
        if (l1.next or l2.next or next1):
            l1 = l1.next if l1.next else ListNode(0)
            l2 = l2.next if l2.next else ListNode(0)
            l1.val += next1
            res.next = self.addTwoNumbers(l1,l2);
        return res;
1
2
3
4
5
6
7
8
9
10