（二）两数相加（Python3）

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

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

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

方法一：循环方法解题

from typing import List

# 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:
        res =  ListNode(10086)
        move = res
        carry = 0
        while l1 != None or l2 != None:
            if l1 == None:
                l1, l2 = l2, l1
            if l2 != None:
                carry, l1.val = divmod((l1.val + l2.val + carry), 10)
                move.next = l1
                l1,l2,move = l1.next,l2.next,move.next
            else:
                carry,l1.val = divmod((l1.val+carry),10)
                move.next = l1
                l1, move = l1.next, move.next
        if carry == 1:
            move.next = ListNode(carry)
        return res.next

方法二： 迭代方法解题

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        def recursive(n1, n2, carry = 0):
            if n1 == None and n2 == None:
                return ListNode(1) if carry == 1 else None
            if n1 == None:
                n1, n2 = n2, n1
                return recursive(n1, None, carry)
            if n2 == None:
                carry, n1.val = divmod((n1.val + carry), 10)
                n1.next = recursive(n1.next, None, carry)
                return n1
            carry, n1.val = divmod((n1.val + n2.val + carry), 10)
            n1.next = recursive(n1.next, n2.next, carry)
            return n1
        return recursive(l1, l2)