[LintCode] 链表求和（简单）

两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。
样例：

输入
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

思路：
两个链表按位相加，关键问题是要注意越界的问题和进位的问题