No.2 Add Two Numbers
原题：
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
题目大意：给出两个链表，存储非负数，两个链表都是按倒序方式存储数字（个位，十位，百位……）要求将两个链表相加并以链表形式返回。
例如：
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807.
那么在分析之前，先回顾下链表的基础知识概念吧（大佬跳过，主要是小詹自己数据结构基础不行）
① 什么是链表？
举个例子：在我们存储一大波数据时，我们很多时候是使用数组，但是当我们执行插入操作的时候就非常麻烦，有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组，我们会怎么做？当然是将5之后的数据往后退一位，然后再插入4,这样非常麻烦，效率也非常低，但是如果用链表，我就直接在3和5之间插入4就行。
链表由一个个节点连接而成，节点结构如下：
其中data部分（数据域）存储数据，next部分（指针域）存储指针，指向下一个节点。任一个链表开始于头指针head，头结点的数据域可以不存储数据。
② 链表基本操作？
初始化链表、链表长度、插入、删除、新增、查找、逆序。具体就不展开了~
回到本题上来~有多少人第一反应是这样子的？举起你的hand:
def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ len_max = max(len(l1),len(l2)) carry = 0 #表示进位，例如9+8 = 17，carry = 1，默认进位为0 for i in range(len_max): l3[i] = l1[i] + l2[i] + carry if l1[i] + l2[i] > 10: carry = 1 else: carry = 0 return l3
以上应该挺好懂的吧，就不去具体讲了（反正这个代码是不对的）
错在哪呢？爱思考的小伙伴应该注意到了，其实思路没有大的问题，毕竟加法我们还是学过的~主要有以下几个小问题：
★ 链表不同于列表数组之类的，不能用len()获取长度
★ 加法计算思考不全面，我们考虑到了存在的进位情况，但是没考虑到链表长度不等，即两个加数位数不等（比如三位数加五位数）
经过对错误代码的反思，我们考虑将题目拆分为两个情况，以三位数加五位数为例，前三位数和前三位数按照我们已有的思路进行处理，第四位第五位则是另一种情况；具体就是：前三位数范围内，对应位进行相加操作时附加上低位的进位；第四位第五位只用将该位加上低位的进位即可（或者理解成另一个三位数的高位为0）具体代码实现如下：
def _addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ #指定到链表头节点 p = dummy = ListNode(-1) #进位标志，低位有进位时为1，默认为0 carry = 0 #当两个链表的同一位置同时不为空时（即小詹举例的低三位数） while l1 and l2: #p.next为指针所指 l1.val为对应的数据 p.next = ListNode(l1.val + l2.val + carry) #除法和求模运算获取p.next的十位个位 carry = p.next.val / 10 p.next.val %= 10 p = p.next l1 = l1.next l2 = l2.next res = l1 or l2 #或运算即对应小詹举得高位例子（第四位第五位） while res: p.next = ListNode(res.val + carry) carry = p.next.val / 10 p.next.val %= 10 p = p.next res = res.next if carry: p.next = ListNode(1) return dummy.next#返回该链表
是不是觉得完事了？敲完代码心里那个舒坦，然而……运行发现有点小错误，这里小詹先不揭秘，下期小詹再告诉大家上述程序在哪一个位置需要调整下才可以噢，找到的小伙伴留言区留下你的看法，第一个答对的有红包噢！而排除了错误的运行效果还比较可观：
如果觉得文章不错，欢迎各种姿势的转发噢，让更多人参与到我们的打卡队伍中来噢！应小伙伴们要求，附建群二维码，谢绝各种推广【小詹自己也不会发除了leetcode打卡之外的公众号文章】，纯打卡讨论群，谢谢各位大佬配合！若超过一百人，可从公众号添加小编微信邀请进群噢！
