Add two numbers问题：给定2个用链表（Linked List）表示的10进制非负整数，求它们的和。
难度：容易
思路：遍历2个链表，按位求和。
陷阱：进位处理；两个链表长度不同
代码：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def addTwoNumbers(self, l1, l2):
carry_over = 0
dummy = end = ListNode(0)
while l1 or l2 or carry_over:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
val = v1 + v2 + carry_over
if val >= 10:
carry_over = 1
val = val - 10
else:
carry_over = 0
end.next = ListNode(val)
end = end.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
以上为常规解法，另有更Pythonic的另类解法，思路是：由于Python可以处理大整数加法，因此只需将两个链表转换成整数后相加，然后再将结果转换为链表即可。（实际运行效率略高于前述标准解法）代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param {ListNode} l1
# @param {ListNode} l2
# @return {ListNode}
def addTwoNumbers(self, l1, l2):
def to_int(l):
return l.val + 10 * to_int(l.next) if l else 0
def to_list(val):
l = ListNode(val % 10)
if val > 9:
l.next = to_list(val / 10)
return l
return to_list(to_int(l1) + to_int(l2))
问题扩展：对于任意多个加数的情况，可以用如下方式处理：
def addTwoNumbers(addends):
dummy = end = ListNode(0)
carry = 0
while addends or carry:
carry += sum(a.val for a in addends)
addends = [a.next for a in addends if a.next]
end.next = end = ListNode(carry % 10)
carry /= 10
return dummy.next
