面试题 02.05. 链表求和

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

Python 解答：
1.常规思路

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(0)
        p = head
        add = 0
        while l1 and l2:
            bit = l1.val+l2.val+add
            if bit >= 10:
                bit -= 10
                add = 1
            else:
                add = 0
            node = ListNode(bit)
            p.next = node
            p = p.next
            l1 = l1.next
            l2 = l2.next
        if add:
            if l1:
                while l1:
                    bit = l1.val + add
                    if bit >= 10:
                        bit -= 10
                        add = 1
                    else:
                        add = 0
                    node = ListNode(bit)
                    p.next = node
                    p = p.next
                    l1 = l1.next
                if add:
                    p.next = ListNode(1)
            elif l2:
                while l2:
                    bit = l2.val + add
                    if bit >= 10:
                        bit -= 10
                        add = 1
                    else:
                        add = 0
                    node = ListNode(bit)
                    p.next = node
                    p = p.next
                    l2 = l2.next
                if add:
                    p.next = ListNode(1)
            elif (not l1) and (not l2):
                p.next = ListNode(1)
        else:
            if l1:
                p.next = l1
            if l2:
                p.next = l2

        return head.next

2.递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def add(l1, l2, carry):
            if (not l1) and (not l2) and (not carry):
                return None
            else:
                bit = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry
                if bit > 9:
                    bit -= 10
                    carry = 1
                else:
                    carry = 0
                node = ListNode(bit)
                node.next = add(l1.next if l1 else None, l2.next if l2 else None, carry)
                return node
        return add(l1, l2, 0)