用python手刃Leetcode(2)：两数相加

青旅半醒 2022-05-22 05:38 131阅读 0赞

> ##### 前言 #####
> 
> 博客里新开一个“用python手刃Leetcode”的专题，顾名思义，主要目的是记录自己在Leetcode上刷题的过程，代码全程用python3编写，所用网址是：[leetcode中国][leetcode]。这个网址的好处是：1）纯中文，解决了英语不好读题困难的问题；2）网页打开速度快。  
> \`  
> 同时可以看到：目前官网给出的解题代码是用java编写的，并没有给出官方的python解答，本专栏除了尽量使用多种解法给出每道题的python3解答代码之外，还会记录下自己在做题过程中的一些收获和思考。便于以后复习查阅。

##### 题目 #####

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

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

> 示例：
> 
> 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

##### 题目分析： #####

**1）** 这道题没有说明链表的长度相同，所以需要考虑链表长度不同的情况。

**2）** 这道题有一个条件：你可以假设除了数字 0 之外，这两个数字都不会以零开头。这就说明，除了单独的一个数字零之外，剩下的这个链表里不会出现以0组成的数字，也就是说可以用是否为0来判断链表是否到了尾巴。

##### 解题必备知识储备 #####

本题中用到了链表这个数据结构。顾名思义，链表就像锁链一样，由一各个节点连在一起，组成一条数据链。每一个节点由两部分组成：数据，下一个数据的位置。其中头节点可以不存储数字，尾节点没有下一个数据的位置。形象表示就是这个：  
![这里写图片描述][70]

链表相对于数组解决的是数据的快速插入，删除问题。比如说：有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组存储，插入时就要将5之后的数据都往后退一位，然后再插入4，这样非常麻烦，但是如果用链表，直接3和5的“链条”断开，然后接上4就行。

链表用C（C++）语言实现最为方便，因为其有指针，可以很方便地在内存中跳来跳去。

而在python中，实现需要用到其动态语言的特性，直接把对象赋值给新的变量。

在解题模板里，其实已经给出了链表类的定义方法，即定义一个ListNode类，然后进行一个初始化（其实也可以把插入，删除等操作定义在链表方法里，这里我们先不管）：

class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None

虽然给出的模板中这段语句是被注释掉的，但是其实LeeCode的官方解释器中已经定义好了这个类，因为类已经定义好，我们按照定义调用即可。比如：创建一个值为1的链表头：`L1 = ListNode(1)`。

理解了以上知识点，下面就开始解题：

##### 方法： #####

class Solution:
        def addTwoNumbers(self, l1, l2):
            """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
            head = R = ListNode(0)
            flag = 0 # 用来标记是否有进位
            while l1 and l2:
                if flag == 1:
                    add = l1.val + l2.val + 1
                    l1 = l1.next
                    l2 = l2.next
                else:
                    add = l1.val + l2.val
                    l1 = l1.next
                    l2 = l2.next       
                if  add>=10 :
                    flag = 1
                    add = add-10
                    R = ListNode(add)
                    R = R.next
                else:
                    flag = 0
                    R = ListNode(add)
                    R = R.next
            return head.next

##### 解题收获： #####

###### 1、收获1 ######

未完待续…………

[leetcode]: https://leetcode-cn.com/
[70]: /images/20220522/46b32e7310cf486a8f4e90bff98ddd8d.png