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

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

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

示例：

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

题目分析：

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

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

解题必备知识储备

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

链表相对于数组解决的是数据的快速插入，删除问题。比如说：有一堆数据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
复制代码