用python语言解答LeetCode的2题
碎碎念（不用看！下一节开始才是重点~~~）
懵逼。。。一脸懵逼。。。两脸懵逼。。。三脸懵逼。。。。n脸懵逼。。。。
截止目前为止还没用Python做过链表相关的题目。。。让我用c语言做我也照样不会。。。还是吃的太饱，，，导致代码量太少。。。好了不废话了，，，我去看看大神们怎么分析问题的
方法一：
将链表转化成数字，将数字进行相加后再转化成链表
这个解题思路很简单，只要能熟练运用Python链表的创建增加操作即可（这么简单的我都没想到。。。）
# 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:
# 先定义一个函数，实现链表转化为数字
def convert_to_num(list):
num = ''
while list != None:
num = str(list.val) + num
list = list.next
return int(num)
# 定义一个函数，实现将数字转化为链表
def convert_to_link(num):
root = ListNode(num % 10)
l3 = root
num = num // 10
while num != 0:
l3.next = ListNode(num % 10)
l3 = l3.next
# l3.val = num % 10
num = num // 10
return root
# 用上面定义的函数convert_to_num将两个链表分别转换为num1和num2
num1, num2 = convert_to_num(l1), convert_to_num(l2)
# 将两个数字相加得到两数之和
num = num1 + num2
# 用函数convert_to_link将两数之和转换为链表
return convert_to_link(num)
这是方法一的运行结果
注1：在这里遇到了一个问题如下
这个是我自己写的代码，在l3.val = num % 10这一行会报错。但是如果我把注释的那一行加上，去掉报错的那一行就OK了。如下代码为正确代码：
我不知道为什么，询问中。。。估计又是个小渣渣才会犯的错误
问过大佬之后，来解释一下。
要将数字转换为链表，必然会创建链表结点，l3.next = ListNode(num % 10)是用来创建链表结点的。
准确的来说这一行有三个作用:
- 创建链表结点
- 给新结点的val属性赋值
- 将新结点链接到当前结点上
将数字转换为链表的过程：
- 创建链表结点
- 给新结点的val属性赋值
- 将新结点链接到当前结点上
- 移动当前结点指针，指向新结点
注2：
这个方法有一个弊端就是没有考虑到int溢出情况，只不过测试用例没有给出这个边界值情况，所以可以通过。
方法二：初等数学法
这个是在官方解答里找到的，也是网上最多的解法，这个方法可以解决方法一的不足之处。下面来看一下思路吧~~~
我们使用变量carry来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
如图，对两数相加方法的可视化：342+465 = 807，每个结点都包含一个数字，并且数字按位逆序存储。
就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表l1和l2的表头开始相加。由于每位数字都应当处于0…9的范围内，我们计算两个数字的和时可能会出现“溢出”。例如，5+7=12.在这种情况下，我们会将当前位的数值设置为2，并将进位carry=1带入下一次迭代。进位carry必定是0或1，这是因为两个数字相加（考虑到进位，可能出现的最大和为9+9+1=19）
伪代码如下：
- 将当前结点初始化为返回列表的哑结点。
- 将进位carry初始化为0
- 将p和q分别初始化为列表l1和l2的头部。
- 遍历列表l1和l2直至到达他们的尾端。
- 将x设为结点p的值。如果p已经到达l1的末尾，则将其值设置为0。
- 将y设为结点q的值。如果q已经到达l2的末尾，则将其值设置为0。
- 设定
sum = x + y + carry - 更新进位的值，
carry = sum / 10 - 创建一个数值为
（sum mod 10）的新结点，并将其设置为当前结点的下一个结点，然后将当前结点前进到下一个结点。 - 同时，将
p和q前进到下一个结点
- 检查
carry = 1是否成立，如果成立，则向返回列表追加一个含有数字1的新结点。 - 返回哑结点的下一个结点。
请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。
哑结点（dummy node）：
哑结点是初始值为NULL的结点，创建在使用到链表的函数中，可以起到避免处理头结点为空的边界问题的作用，减少代码执行异常的可能性。
也就是说，使用哑结点可以起到简化代码的作用（可以省略当函数的入口参数为空时的判断）。
请特别注意以下情况：
方法二的代码（一）（自己根据官方解答修改版）
# 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(0)
p, q = l1, l2
curr = root
carry = 0
while p or q:
x = p.val if p else 0
y = q.val if q else 0
sum = carry + x + y
carry = sum // 10
curr.next = ListNode(sum % 10)
curr = curr.next
if p != None:
p = p.next
if q != None:
q = q.next
if carry > 0:
curr.next = ListNode(carry)
return root.next
方法二的运行结果（一）
方法二的代码（评论区大佬版）
# 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:
re = ListNode(0)
r=re
carry=0
while(l1 or l2):
x= l1.val if l1 else 0
y= l2.val if l2 else 0
s=carry+x+y
carry=s//10
r.next=ListNode(s%10)
r=r.next
if(l1!=None):l1=l1.next
if(l2!=None):l2=l2.next
if(carry>0):
r.next=ListNode(1)
return re.next
方法二的运行结果（二）
这里有几个点不太明白（其实这些问题完全是因为链表那块没学好，打算边刷题边学习链表，这样学习会比现在去系统的看一遍链表的知识有效率）
1.为什么要将p和q分别初始化为列表l1和l2的头部，在评论区里有位大佬的代码中没有设置p和q也可以执行，设置了p和q之后有什么优势？
2.如上代码中一直操作的是curr为什么返回curr.next是个空列表，返回root.next则是结果
自己想了一下，这个感觉是因为curr.next返回的是当前结点的下一位结点，而这个结点不存在，所以为空。root.next则是从表头开始的，所以包含整个链表的内容
3.官方解答说要用哑结点，Python中的哑结点是怎么体现的？
注：下面这个代码是自己没看参考写的，测试后显示超出时间限制，仔细检查之后发现是因为忘记将p和q前进到下一个结点了，所以应该是while陷入死循环了
正确代码请见方法二的代码（一）（自己根据官方解答修改版）
# 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(0)
curr = root
p, q = l1, l2
carry = 0
while p or q:
x = p.val if p else 0
y = q.val if q else 0
sum = x + y + carry
carry = sum // 10
curr.next = ListNode(sum % 10)
curr = curr.next
if carry > 0 :
curr.next = ListNode(carry)
curr = curr.next
return root.next
还有一个问题是我在最后处理进位的时候加了一个curr = curr.next,，发现对运行结果并没有什么影响。这个操作会有什么隐患吗？
方法二的运行结果（三）
这个是我的代码修改之后的运行结果
本篇博客有三个问题未解答，后序会将解答补上
Reference：
1.Python链表https://www.cnblogs.com/kumata/p/9147077.html
2.思路一https://www.bilibili.com/video/av49891425?from=search&seid=6850040659988646714
3.思路二https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
