No2.Add Two Numbers

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

思路：

1.逆序存储比较好解决，顺序存储就比较麻烦。用一个变量 carry 来存储每个位上和的进位
2.如果不想使用 O(n)的空间，那就必须在原来的链表上存储，找出两个链表中较长的那一个链表用来存储.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        ##9999+1
        ##使用 list3来标注较长的那个链表
        def longer(l1,l2):    ##找出较长的那个链表
            start1=l1
            start2=l2
            while start1 and start2:
                start1=start1.next
                start2=start2.next
            if start1:
                return l1
            else:
                return l2
        l3=longer(l1,l2)
        carry=0
        start1=l1         ##标注三个链表的头，以便进行遍历
        start2=l2
        start3=l3
        while start1 or start2:
            if start1 and start2:    
                val = start1.val+start2.val+carry
                start1=start1.next
                start2=start2.next
            elif start1:
                val = start1.val+carry
                start1=start1.next
            else:
                val = start2.val+carry
                carry=0
                start2=start2.next
            if val>9:       ##如果两个位的和大于等于10，更新 carry 和 val
                carry=1
                val=val-10
            else:           ##否则将 carry 复位
                carry=0
            start3.val=val
            if start3.next:     ##如果较长的那个链表还未到最后一个结点，则继续，否则，判断进位是否为1 ，为1 则创建新结点放在整个链表的最后面
                start3=start3.next
            else:
                if carry == 1:
                    last=ListNode(1)
                    start3.next=last
        return l3