2. 两数相加

Gnomeshgh

一、题目描述


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

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

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



示例 1：


输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 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]


提示：

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


二、解题思路


（一）暴力解
将链表转换为数字然后相加，最后在取每一个位进行插入链表。

1. 
   
2. # 链表转为数字
   
3. def listNodeToNum(listnode):
   
4.     # 保存最后的结果
   
5.     num = 0
   
6.     # 每次取一个数之后，会扩大十倍
   
7.     count = 1
   
8.     # 当链表为None时结束循环
   
9.     while listnode:
   
10.         num = num + count * listnode.val
    
11.         count = count * 10
    
12.         listnode = listnode.next
    
13.     return num
    
14. 
    
15. # 采用尾插法
    
16. def numToListNode(num):
    
17.     head = ListNode(num % 10)
    
18.     rear = head
    
19.     # 去掉个位
    
20.     num = num // 10
    
21.     # 当num为0时退出循环
    
22.     while num:
    
23.         node = ListNode(num % 10)
    
24.         rear.next = node
    
25.         rear = node
    
26.         # 去掉个位
    
27.         num = num // 10
    
28.     return head
    
29. 
    
30. class Solution:
    
31.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    
32.         # 将链表转为数字
    
33.         num1 = listNodeToNum(l1)
    
34.         num2 = listNodeToNum(l2)
    
35. 
    
36.         # 将数字相加
    
37.         num2 = num2 + num1
    
38. 
    
39.         #将数字转为链表
    
40.         result = numToListNode(num2)
    
41. 
    
42.         return result
    

复制代码

（二）双指针直接相加
两个指针分别指向两个链表的头部，依次取出数值，然后相加，结果取个位将十位进位。依次循环。
将加和的数字进行尾插。

1. class Solution:
   
2.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
   
3.         # 保存链表头部，以及当前指针
   
4.         dummy = curr = ListNode(0)
   
5.         # 进位标志
   
6.         carry = 0
   
7.         
   
8.         # 如果两个链表都为空且进位为0就退出循环
   
9.         while l1 or l2 or carry:
   
10.             # 如果链表不为空就取值，为空就赋值为0
    
11.             val1 = l1.val if l1 else 0
    
12.             val2 = l2.val if l2 else 0
    
13.             
    
14.             # 直接取进位和个位
    
15.             carry, out = divmod(val1 + val2 + carry, 10)
    
16.             
    
17.             # 插入链表
    
18.             curr.next = ListNode(out)
    
19.             curr = curr.next
    
20.             
    
21.             # 链表指针后移
    
22.             l1 = l1.next if l1 else None
    
23.             l2 = l2.next if l2 else None
    
24.         
    
25.         return dummy.next

复制代码