445 两数相加II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

进阶：

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：

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

解法

• 创建a,b两个栈，时间复杂度O(M+N)，空间复杂度O(M+N)

# 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:
        pre = None
        a,b = [],[]
        while l1:
            a.append(l1.val)
            l1 = l1.next
        while l2:
            b.append(l2.val)
            l2 = l2.next
        extra = 0
        while a or b or extra:
            if a:
                x = a.pop()
            else:
                x = 0
            if b:
                y = b.pop()
            else:
                y = 0
            node = ListNode((x+y+extra)%10)
            extra = (x+y+extra)//10
            node.next = pre
            pre = node
        return pre

• 将a，b两个非空链表反转，然后按照第2题解法，再反转一次就可输出结果。实际上，该方法由第一种方法发展而来。

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

7 -> 2 -> 4 -> 3 反转 3 -> 4 -> 2 -> 7
5 -> 6 -> 4 反转 4 -> 6 -> 5
按第2题方法相加，得
7 -> 0 -> 8 -> 7。 反转得
7 -> 8 -> 0 -> 7