【记录帖】（No.002）从零打卡刷Leetcode

写在前边：

小詹一直觉得自己编程能力不强，想在网上刷题，又怕不能坚持。不知道有木有和小伙伴和小詹一样想找个人一起刷题呢？欢迎和小詹一起定期刷leetcode，每周一周五更新一题，每一题都吃透，欢迎一题多解，寻找最优解！欢迎小伙伴们把自己的思路在留言区分享出来噢~

前期回顾：（附上使用频繁的排序算法python版）第一期的题目，有小伙伴分享了新的更优方法，可以看往期的置顶留言。

【记录帖】（No.001）从零打卡刷Leetcode

程序员面试必备之排序算法汇总(上)

程序员面试必备之排序算法汇总(下)

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#返回该链表

是不是觉得完事了？敲完代码心里那个舒坦，然而……运行发现有点小错误，这里小詹先不揭秘，下期小詹再告诉大家上述程序在哪一个位置需要调整下才可以噢，找到的小伙伴留言区留下你的看法，第一个答对的有红包噢！而排除了错误的运行效果还比较可观：