Add two numbers問題：給定2個(gè)用鏈表（Linked List）表示的10進(jìn)制非負(fù)整數(shù)，求它們的和。
難度：容易
思路：遍歷2個(gè)鏈表兼蕊，按位求和。
陷阱：進(jìn)位處理件蚕；兩個(gè)鏈表長度不同
代碼：
# 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
以上為常規(guī)解法孙技，另有更Pythonic的另類解法，思路是：由于Python可以處理大整數(shù)加法排作，因此只需將兩個(gè)鏈表轉(zhuǎn)換成整數(shù)后相加牵啦，然后再將結(jié)果轉(zhuǎn)換為鏈表即可。（實(shí)際運(yùn)行效率略高于前述標(biāo)準(zhǔn)解法）代碼如下：
# 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))
問題擴(kuò)展：對于任意多個(gè)加數(shù)的情況妄痪，可以用如下方式處理：
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
