一、题目

Add Two Numbers

二、解题

---

1）题意

给出两个链表，把对应位置上的值进行十进制相加（有进位），返回链表的根节点。

2）输入输出说明

输入：两个列表的根节点（并不是整个列表，即leetcode会把默认生成好的列表的根节点传入）
输出：累加之后的根节点

3）关键点

1）做十进制加法时，使用和％10来得出当前位的值，使用／10来得出进位。
2）如果用常规解法，在处理不同长度的两个链表是比较麻烦的。因此我使用了标记的方法：

• 当某个链表的next为空了，把其值（val）赋值为-1（题意中所有值都为非负数，所以－1可以作为一个标示，不会影响到原本的值）。
• 在两个值相加之前，当检测到存在值为-1的时候，把值变成0，再进行相加（因为是加0，所以并不影响结果）
• 跳出条件是两个链表的值都为-1。
• 最后要判断一次进位的值是否不为0，如果不为0，需要补上一个node

4）为什么要赋值为-1，而不是直接赋值为0

因为如果直接赋值为0，可能存在列表 3,0,3，即原本值就是0，而不是代表链表结束了，这样会影响到链表。

三、尝试与结果

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        resultNode = None
        add = 0
        while True:
            #当val为-1的时候，说明已经有list遍历完了，这个时候需要把val变成0
            if l1.val == -1:
                l1.val = 0
            if l2.val == -1:
                l2.val = 0

            tSum = (l1.val + l2.val + add) % 10
            add = (l1.val + l2.val + add) / 10
            listn = ListNode(tSum)

            if resultNode == None:
                resultNode = listn
                flagNode = resultNode
            else:
                flagNode.next = listn
                flagNode = flagNode.next

            if l1.next != None:
                l1 = l1.next
            else:
                #直接改变当前的节点的值
                l1.val = -1

            if l2.next != None:
                l2 = l2.next
            else:
                l2.val = -1
            #两个都为-1了，说明两个列表都遍历完了
            if l1.val == -1 and l2.val == -1:
                break

        if add != 0:
            listn = ListNode(add)
            flagNode.next = listn

        return resultNode

结果：AC

四、完整调试代码

class ListNode(object):
     def __init__(self, x):
         self.val = x
         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        resultNode = None
        add = 0
        while True:
            if l1.val == -1:
                l1.val = 0
            if l2.val == -1:
                l2.val = 0

            tSum = (l1.val + l2.val + add) % 10
            add = (l1.val + l2.val + add) / 10
            listn = ListNode(tSum)

            if resultNode == None:
                resultNode = listn
                flagNode = resultNode
            else:
                flagNode.next = listn
                flagNode = flagNode.next

            if l1.next != None:
                l1 = l1.next
            else:
                l1.val = -1

            if l2.next != None:
                l2 = l2.next
            else:
                l2.val = -1

            if l1.val == -1 and l2.val == -1:
                break

        if add != 0:
            listn = ListNode(add)
            flagNode.next = listn

        return resultNode

if __name__ == '__main__':
    print "----------------- start -----------------"

    l1_1 = ListNode(2)
    l1_2 = ListNode(4)
    l1_3 = ListNode(3)
    l1_1.next = l1_2
    l1_2.next = l1_3

    l2_1 = ListNode(5)
    l2_2 = ListNode(6)
    l2_3 = ListNode(4)
    l2_1.next = l2_2
    l2_2.next = l2_3

    l3_1 = Solution().addTwoNumbers(l1_1,l2_1)
    while l3_1 != None:
        print l3_1.val
        l3_1 = l3_1.next