LeetCode题解2：Add two numbers

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