LeetCode-445-两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

image.png

解题思路：

1. 不能翻转列表，用栈来存储；
2. 先用两个栈将链表存储起来，然后依次遍历栈的末位，即个十百千万的顺序；
3. 考虑进位问题。
   Python3代码：

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1 = [] 
        stack2 = []
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next
        
        carry = 0
        result = None 
        while stack1 or stack2 or carry==1:
            num1 = stack1.pop() if stack1 else 0
            num2 = stack2.pop() if stack2 else 0
            p = ListNode(0)
            if num1 + num2 + carry > 9:
                p.val = num1 + num2 + carry - 10
                carry = 1
            else:
                p.val = num1+num2+carry
                carry = 0
            p.next = result 
            result = p 
        return result