445.Add Two Numbers II.md

基本思路

• 最直接的想法就是先翻转链表.
• 不过本题也说了，如果不让你反转链表怎么办？其实也好办，我们可以利用栈这种先进后出的数据结构，把链表节点从头到尾放进栈中，再从栈拿出来就是从尾到头的顺序，相当于是反转链表的效果，然后又回到了第 2 题的加法逻辑。

栈 + 双指针

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        stack1, stack2, stack = [], [], []
        p1, p2 = l1, l2

        # 把链表元素转入栈中
        while p1:
            stack1.append(p1.val)
            p1 = p1.next
        while p2:
            stack2.append(p2.val)
            p2 = p2.next

        # 记录进位
        carry = 0
        # 两条链表走完且**没有进位**时才能结束循环
        while stack1 or stack2 or carry:
            cur1 = stack1.pop() if stack1 else 0
            cur2 = stack2.pop() if stack2 else 0
            res = cur1 + cur2 + carry

            carry = res // 10
            res %= 10
            stack.append(res)

        # 把栈里的数取出来构建链表
        p = dummy = ListNode(-1)
        while stack:
            p.next = ListNode(stack.pop())
            p = p.next

        return dummy.next

这题也可以不用stack直接在while循环最后构建链表:

dummy = ListNode(-1)
...
while stack1 or stack2 or carry:
  ...
  # 构建新节点，直接接在 dummy 后面
  newNode = ListNode(res)
  newNode.next = dummy.next
  dummy.next = newNode

return dummy.next