两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
样例：
输入
3->1->5->null
5->9->2->null
输出
8->0->8->null
解决方案
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param l1: the first list
@param l2: the second list
@return: the sum list of l1 and l2
"""
def addLists(self, l1, l2):
# write your code here
if l1 is None:
return l2
elif l2 is None:
return l1
else:
flag = False
result = ListNode(0)
tmp = l1.val + l2.val
if flag:
tmp += 1
flag = False
if tmp >= 10:
flag = True
tmp = tmp - 10
result.val = tmp
result.next = ListNode(0)
cycle = result
l1=l1.next
l2=l2.next
while(l1 is not None and l2 is not None):
cycle = cycle.next
tmp = l1.val + l2.val
if flag:
tmp += 1
flag = False
if tmp >= 10:
flag = True
tmp = tmp - 10
cycle.val = tmp
cycle.next = ListNode(0)
l1=l1.next
l2=l2.next
if l1 is None and l2 is None:
if flag:
cycle = cycle.next
cycle.val = 1
cycle.next = None
flag = False
else:
cycle.next = None
else:
final = l1 if l1 is not None else l2
while(final is not None):
cycle = cycle.next
if flag:
cycle.val = final.val + 1
if cycle.val >= 10:
cycle.val -= 10
else:
flag = False
else:
cycle.val = final.val
cycle.next = ListNode(0)
final = final.next
if flag:
cycle = cycle.next
cycle.val = 1
cycle.next = None
else:
cycle.next = None
return result
思路：
两个链表按位相加，关键问题是要注意越界的问题和进位的问题
