2-两数相加

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

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

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

示例：

​ 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) ​ 输出：7 -> 0 -> 8 ​ 原因：342 + 465 = 807

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers

本操作类似大数字的加法，思想类似循环字符串大数字的相加。

再加上链表的基本操作，包括两个链表的连接。

一开始思想比较混乱的时候，脑子里怎么想的就怎么来，写出如下代码：

def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        flag = 0
        ret = []
        while l1 != None and l2 !=None:
            midNum = l1.val + l2.val + flag
            if midNum >= 10:
                flag, midNum = divmod(midNum, 10)
            else:
                flag = 0
            ret.append(midNum)
            l1 = l1.next
            l2 = l2.next
        l3 = ListNode(ret[0])
        mid = l3
        if l1 == None and l2 == None and flag != 0:
            ret.append(flag)
            flag = 0
        for i in ret[1:]:
            mid.next = ListNode(i)
            mid = mid.next
        l1 = l1 if l1 else l2
        while l1 != None and flag != 0:
            midNum = l1.val + flag
            if midNum >= 10:
                flag, midNum = divmod(midNum, 10)
            else:
                flag = 0
            mid.next = ListNode(midNum)
            l1 = l1.next
            mid = mid.next
        if l1 != None:
            mid.next = l1
        if flag != 0:
            while mid.next!=None:
                mid = mid.next
            mid.next = ListNode(flag)
        return l3

flag用来判断是否需要进位。

ret是一个辅助工具，用来存储相加后得到的值，然后再转成ListNode，原因是无法写出动态生成l3的链表（自己太菜，后来去掉了这个辅助）

然后divmod(除数，被除数)函数返回一个元组tuple（商，余数）。我们的商就用来增加l3的节点，余数就作为进位判断。

在一开始，需要处理短链表的全部和长链表等长的部分。

整体思路如上。代码实现就如上了。

接下来进行一些合并，去除掉一些不必要的代码：

def addTwoNumbers2(self, l1, l2):
        target = ListNode(0)  # 作为根节点的引用
        p = target
        add = 0  # 作为上一次相加是否需要进1的依据
        while l1 and l2:
            p.next = ListNode((l1.val + l2.val + add) % 10)
            add = (l1.val + l2.val + add) // 10
            p, l1, l2 = p.next, l1.next, l2.next
        l1 = l1 if l1 else l2
        while add:
            if l1:
                p.next = ListNode((l1.val + add) % 10)
                add = (l1.val + add) // 10
                p, l1 = p.next, l1.next
            else:
                p.next = ListNode(add)
                p = p.next
                break
        p.next = l1
        return target.next

为了去掉ret数组，我们在一开始直接初始化ListNode(0)作为头结点（返回的时候返回target.next）即可去掉头结点

在两链表一一对应的部分，我们执行如下代码：

while l1 and l2:
	p.next = ListNode((l1.val + l2.val + add) % 10)
	add = (l1.val + l2.val + add) // 10
	p, l1, l2 = p.next, l1.next, l2.next

然后经过这一步赋值操作，则可以得到剩下的链表或者空：

l1 = l1 if l1 else l2

接下来判断是否需要进位，如果不需要，则直接追加剩余部分或空：

p.next = l1

如果需要进位

while add:
	if l1:
		p.next = ListNode((l1.val + add) % 10)
		add = (l1.val + add) // 10
		p, l1 = p.next, l1.next
	else:
		p.next = ListNode(add)
        p = p.next
        break

则判断剩余长链表是否有值，如果没有，则直接追加要进位的 1（else语句）

如果有，则执行if里面的语句，进行两数相加，直到不需要进位，最后直接追加剩余部分就可以了。

以上的条件分支比第一次少了很多，主要是要头脑清晰。

再来分析一下第二次所做的判断。

在处理到两者相等的时候，不去思考是否有剩余的值，先判断是否需要进位，在有进位的基础下，合并了一部分操作。具体需要自行体会。

思考顺序和角度不同写出来的代码也不同。无所谓对错。

两种方案的耗时和空间使用都差不多，只是第一种代码量少一点。比较符合常规的思考。

第二种需要在第一种的基础上进行更深层次的思考。