Stefan Pochmann 的上帝之手（5）两数相加

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8

原因：342 + 465 = 807

解法1：

普通写法（12行）

def addTwoNumbers(self, l1, l2):
    """
    :type l1: ListNode
    :type l2: ListNode
    :rtype: ListNode
    """
    carry = 0
    res = p = ListNode(-1)
    while l1 or l2 or carry:
        l1v = l1.val if l1 else 0
        l2v = l2.val if l2 else 0
        s = l1v + l2v + carry
        carry = s / 10
        p.next = ListNode(s % 10)
        p = p.next
        l1 = l1.next if l1 else None
        l2 = l2.next if l2 else None
    return res.next

Pochmann 的写法（9行）

这个写法不仅省代码，还可以轻易扩充到多个数相加。

def addTwoNumbers(self, l1, l2):
    addends = l1, l2
    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

解法2（上帝之手，8行）：

把链表换算为整数，求和后换算会列表。

def addTwoNumbers(self, l1, l2):
    def toint(node):
        return node.val + 10 * toint(node.next) if node else 0
    def tolist(n):
        node = ListNode(n % 10)
        if n > 9:
            node.next = tolist(n / 10)
        return node
    return tolist(toint(l1) + toint(l2))

或者：

def addTwoNumbers(self, l1, l2):
    def toint(node):
        return node.val + 10 * toint(node.next) if node else 0
    n = toint(l1) + toint(l2)
    first = last = ListNode(n % 10)
    while n > 9:
        n /= 10
        last.next = last = ListNode(n % 10)
    return first