一、题目
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
