两数相加 II 图解题解

这道题到底在问什么

输入

A=846729583, B=358496857

输出

1205226440

最优解：一步一步想明白

1. 3思路一句话：用栈把「高位在前」翻成「低位先出」，再逐位相加、头插结果，就回到了熟悉的竖式加法。下面一步步演给你看。
2. 4上两行是 A、B（高位在前，头节点是最高位），最下一行是结果。先把 A、B 各压进一个栈，进位 carry 从 0 开始。
3. 5两个栈顶都指向各自的最低位（最右节点）。我们从这里开始逐位弹栈相加，结果从右往左、用头插法一格格补上。
4. 6弹出两个栈顶（第 0 低位）：a=3，b=7，进位 carry=0。cur = 3+7+0 = 10。
5. 710 % 10 = 0，头插到结果最前面（这一格）；10 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
6. 8弹出两个栈顶（第 1 低位）：a=8，b=5，进位 carry=1。cur = 8+5+1 = 14。
7. 914 % 10 = 4，头插到结果最前面（这一格）；14 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
8. 10弹出两个栈顶（第 2 低位）：a=5，b=8，进位 carry=1。cur = 5+8+1 = 14。
9. 1114 % 10 = 4，头插到结果最前面（这一格）；14 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
10. 12弹出两个栈顶（第 3 低位）：a=9，b=6，进位 carry=1。cur = 9+6+1 = 16。
11. 1316 % 10 = 6，头插到结果最前面（这一格）；16 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
12. 14弹出两个栈顶（第 4 低位）：a=2，b=9，进位 carry=1。cur = 2+9+1 = 12。
13. 1512 % 10 = 2，头插到结果最前面（这一格）；12 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
14. 16弹出两个栈顶（第 5 低位）：a=7，b=4，进位 carry=1。cur = 7+4+1 = 12。
15. 1712 % 10 = 2，头插到结果最前面（这一格）；12 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
16. 18弹出两个栈顶（第 6 低位）：a=6，b=8，进位 carry=1。cur = 6+8+1 = 15。
17. 1915 % 10 = 5，头插到结果最前面（这一格）；15 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
18. 20弹出两个栈顶（第 7 低位）：a=4，b=5，进位 carry=1。cur = 4+5+1 = 10。
19. 2110 % 10 = 0，头插到结果最前面（这一格）；10 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
20. 22弹出两个栈顶（第 8 低位）：a=8，b=3，进位 carry=1。cur = 8+3+1 = 12。
21. 2312 % 10 = 2，头插到结果最前面（这一格）；12 >= 10 ? 是 → 进位 carry 变为 1，带到更高一位。
22. 24两个栈都空了，但 carry 还是 1！别漏：要再头插一个最高位节点 1。
23. 25头插最高位 1，结果链表完成（高位在前）：1205226440（即 1205226440）。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def addTwoNumbers(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:
        a = s1.pop() if s1 else 0
        b = s2.pop() if s2 else 0
        carry, d = divmod(a + b + carry, 10)
        node = ListNode(d); node.next = head; head = node  # 头插
    return head

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2){
    stack<int> s1, s2;
    for(; l1; l1 = l1->next) s1.push(l1->val);
    for(; l2; l2 = l2->next) s2.push(l2->val);
    int carry = 0; ListNode* head = nullptr;
    while(!s1.empty() || !s2.empty() || carry){
        int a = s1.empty()?0:s1.top(); if(!s1.empty()) s1.pop();
        int b = s2.empty()?0:s2.top(); if(!s2.empty()) s2.pop();
        int s = a + b + carry; carry = s / 10;
        ListNode* node = new ListNode(s % 10);
        node->next = head; head = node;   // 头插
    }
    return head;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Deque<Integer> s1 = new ArrayDeque<>(), s2 = new ArrayDeque<>();
    for (; l1 != null; l1 = l1.next) s1.push(l1.val);
    for (; l2 != null; l2 = l2.next) s2.push(l2.val);
    int carry = 0; ListNode head = null;
    while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
        int a = s1.isEmpty() ? 0 : s1.pop();
        int b = s2.isEmpty() ? 0 : s2.pop();
        int s = a + b + carry; carry = s / 10;
        ListNode node = new ListNode(s % 10);
        node.next = head; head = node;   // 头插
    }
    return head;
}

复杂度

面试官可能追问