两数相加 II 图解题解

这道题到底在问什么

l1,l2

[7,2,4,3],[5,6,4]

输出

[7,8,0,7]

先想最直接的笨办法

链表指针跟着代码走：推进语句是：s1.append(l1.val)。处理过的部分不再重新枚举。（动画第 10 步）

最优解：一步一步想明白

1. 3下面 9 步动画会按主解代码推进，而不是泛泛讲题型。
2. 4先读清 两数相加 II 的输入输出链表指针跟着代码走：先把示例输入映射到代码参数：def addTwoNumbers(self, l1, l2):。
3. 5s1 = []；s2 = []链表指针跟着代码走：开局只立住必要变量：s1 = []；s2 = []。
4. 6while l1:链表指针跟着代码走：主流程从这里开始：while l1:。
5. 7if s1:链表指针跟着代码走：题目条件落到这一行：if s1:。
6. 8total += s1.pop()链表指针跟着代码走：对应代码：total += s1.pop()。这一行决定当前轮对答案有什么贡献。
7. 9用栈反向处理低位链表指针跟着代码走：边界跟着代码看：total += s2.pop()。
8. 10s1.append(l1.val)链表指针跟着代码走：推进语句是：s1.append(l1.val)。处理过的部分不再重新枚举。
9. 11return head链表指针跟着代码走：到这里，carry 已经能表达题目要求。
10. 12return：return head链表指针跟着代码走：最后检查返回形态：返回值、原地修改或设计类状态，要和 LeetCode 判题方式一致。
11. 15记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。

⚠️ 容易写错的地方

完整代码（Python）

class Solution:
    def addTwoNumbers(self, l1, l2):
        s1 = []
        s2 = []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        carry = 0
        head = None
        while s1 or s2 or carry:
            total = carry
            if s1:
                total += s1.pop()
            if s2:
                total += s2.pop()
            node = ListNode(total % 10)
            node.next = head
            head = node
            carry = total // 10
        return head

复杂度

面试官可能追问