445_两数相加_II

类型：链表

• 445. 两数相加 II 💛

  https://leetcode-cn.com/problems/add-two-numbers-ii/

  ❓ 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加，同样以链表返回。除了数字 0 之外，这两个数字都不会以零开头。

  💡 栈

  把链表元素压入两个栈，再逐一弹出相加。

  class Solution:
      def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
          s1, s2 = [], []
          while l1:
              s1.append(l1.val)
              l1 = l1.next
          while l2:
              s2.append(l2.val)
              l2 = l2.next
          ans = None
          carry = 0
          while s1 or s2 or carry != 0:
              a = 0 if not s1 else s1.pop()
              b = 0 if not s2 else s2.pop()
              cur = a + b + carry
              carry = cur // 10
              cur %= 10
              curnode = ListNode(cur)
              curnode.next = ans
              ans = curnode
          return ans

  时间复杂度：O(max(m, n))，空间复杂度：O(m + n)