給定兩個(gè)非空鏈表來表示兩個(gè)非負(fù)整數(shù)，位數(shù)按逆序存儲(chǔ)，每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字缸剪，兩數(shù)相加返回一個(gè)新的鏈表
思路：
1.逆序存儲(chǔ)比較好解決，順序存儲(chǔ)就比較麻煩东亦。用一個(gè)變量 carry 來存儲(chǔ)每個(gè)位上和的進(jìn)位
2.如果不想使用 O(n)的空間杏节，那就必須在原來的鏈表上存儲(chǔ)，找出兩個(gè)鏈表中較長(zhǎng)的那一個(gè)鏈表用來存儲(chǔ).
# 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來標(biāo)注較長(zhǎng)的那個(gè)鏈表
def longer(l1,l2): ##找出較長(zhǎng)的那個(gè)鏈表
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 ##標(biāo)注三個(gè)鏈表的頭典阵，以便進(jìn)行遍歷
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: ##如果兩個(gè)位的和大于等于10奋渔，更新 carry 和 val
carry=1
val=val-10
else: ##否則將 carry 復(fù)位
carry=0
start3.val=val
if start3.next: ##如果較長(zhǎng)的那個(gè)鏈表還未到最后一個(gè)結(jié)點(diǎn)，則繼續(xù)壮啊，否則嫉鲸，判斷進(jìn)位是否為1 ，為1 則創(chuàng)建新結(jié)點(diǎn)放在整個(gè)鏈表的最后面
start3=start3.next
else:
if carry == 1:
last=ListNode(1)
start3.next=last
return l3
