LeetCode 445. 两数相加 II

约 6 分钟
文章信息 21 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 腾讯 字节 阿里 华为 微软 亚马逊 美团 拼多多 小米 百度 网易 快手 虾皮 猿辅导 作业帮
标签
数学 栈 链表

题目描述

✅ 445. 两数相加 II

image-20260928200828073

image-20260928200828074

题意分析

两个非空链表分别表示非负整数，每个节点保存一位十进制数字，最高位位于链表头部。计算两个整数之和，用同样的高位在前顺序返回一条新链表。

输入可能位数不同；除整数零本身外，没有前导零。加法需要从个位对齐，并逐位向高位传递进位，不能直接把两个链表头当作相同位数。链表可以表示很长的整数，不能依赖把整条链表转换成普通整数再相加。题目进阶还要求不反转输入链表。

解法：栈逆序取位后头插结果

核心思路

[!blue]

单链表只能从高位向低位访问，而加法需要从低位开始。分别遍历两条链表，把每一位顺序压栈，最后压入的最低位就位于栈顶；同时弹出两个栈时，取得的恰好是相同位权上的数字，也自然完成了不同长度数字的右侧对齐。

每轮令 sum 先等于上一位传来的 carry，再加上两个栈各自可弹出的数字。某个栈已经为空，就相当于该数在更高位补零。当前位结果是 sum % 10，传给下一位的进位是 sum / 10；两位数字与进位的和最多为 19，不需要保存整个大整数。

算出的顺序仍是从低位到高位，所以结果不能直接尾插。每生成一位，都新建节点并插到结果头部：新节点指向旧 head，再让 head 指向它。这样已经算出的低位始终留在后面，新算出的更高位放在前面，最终顺序与题意一致。

只要任一栈还有数字，或 carry 不为零，就需要继续。两个栈都空但还有进位时，这轮会创建额外的最高位；两输入都表示零时，也会正常处理已有的零位并得到一个零节点。

遍历时移动的是局部链表指针，原节点的 next 从未修改；新结果的节点单独创建。因此栈负责逆向读取，头插负责输出顺序，同时满足不反转输入的进阶要求。

解题步骤

  1. 遍历两条链表，分别把数位压入两个栈。
  2. 初始化 carry = 0、结果头 head 为空。
  3. 在两栈至少一个非空或仍有进位时，以旧进位初始化 sum，再从非空栈各取一位累加。
  4. 新建值为 sum % 10 的节点，先连接旧 head，再将它设为新头。
  5. 更新 carry = sum / 10，处理下一高位；循环结束返回 head。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();

        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode head = null;

        // 低位从栈顶取，输入耗尽后的最后进位也要继续处理。
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int sum = carry;

            if (!stack1.isEmpty()) {
                sum += stack1.pop();
            }

            if (!stack2.isEmpty()) {
                sum += stack2.pop();
            }

            ListNode node = new ListNode(sum % 10);

            // 新生成的是更高一位，用头插保持最终链表从高到低。
            node.next = head;
            head = node;
            carry = sum / 10;
        }

        return head;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := make([]int, 0)
    stack2 := make([]int, 0)
    for l1 != nil {
        stack1 = append(stack1, l1.Val)
        l1 = l1.Next
    }
    for l2 != nil {
        stack2 = append(stack2, l2.Val)
        l2 = l2.Next
    }

    carry := 0
    var head *ListNode
    // 低位从栈顶取，输入耗尽后的最后进位也要继续处理。
    for len(stack1) > 0 || len(stack2) > 0 || carry != 0 {
        sum := carry
        if len(stack1) > 0 {
            sum += stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }
        if len(stack2) > 0 {
            sum += stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }

        // 新生成的是更高一位，用头插保持最终链表从高到低。
        node := &ListNode{Val: sum % 10, Next: head}
        head = node
        carry = sum / 10
    }
    return head
}

复杂度分析

  • 时间复杂度：$O(m + n)$，两条链表的长度分别为 m、n。每个数位入栈、出栈各一次，最后至多多处理一位进位。
  • 空间复杂度：$O(m + n)$，两个栈保存输入数位。不计返回链表，其长度最多为 max(m, n) + 1。

关键点总结

[!green]

  • 栈把输入读取顺序变为低位在前，不同长度也会自动按个位对齐。
  • 头插把逐位计算结果重新组织为高位在前。
  • 结束条件同时检查两份输入和进位，三者全部耗尽才算完成。

易错点总结

[!yellow]

  • 循环要求两栈都非空，会漏掉较长输入剩余的高位；应使用“至少一个非空”。
  • 两栈空后立即结束，会漏掉最后新增的最高进位。
  • 用尾插保存逐位结果，会让最终链表变成低位在前。
  • 头插时先覆盖 head，再设置新节点后继，可能丢掉旧结果或形成自环。
  • 从两条链表的头直接逐位相加，会把高位位置错误对齐，也无法提前知道低位进位。
  • 用固定宽度整数保存整条链表的值，会在合法的长输入上溢出。

相似题目

题目 难度 关联与区别
2. 两数相加 中等 原题低位在前，可顺序处理进位；本题高位在前，用栈或反转才能从低位开始。
415. 字符串相加 简单 同样模拟逐位加法，字符串可直接从末尾向前索引，链表需要补足逆向访问能力。
66. 加一 简单 逐位计算并维护进位；本题高位在前需反转或栈辅助，该题加一时只传播单次进位。
67. 二进制求和 简单 逐位计算并维护进位；本题高位在前需反转或栈辅助，该题按二进制位相加。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/73476589
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！