LeetCode LCR 025. 两数相加 II

约 5 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数学 栈 LCR 链表

题目描述

✅ LCR 025. 两数相加 II

image-20260928235040825

image-20260928235040826

题意分析

两条非空链表分别表示非负整数，每个节点是一位十进制数，最高位在头部。求两数之和，并返回同样高位在前的新链表。

数字可能很长，不能先装进固定宽度整数再相加。两条链长度可以不同，计算要从个位向高位传递进位。下面用双栈完成计算，同时满足不能翻转输入链表的进阶要求。

解法：双栈从低位相加与头插

核心思路

[!blue]

加法依赖低位传来的进位，但单链表只能从高位往低位访问。分别将两个链表的数位按顺序压栈，最后进入的个位就会最先弹出，栈把读取方向转换成了计算方向。

每轮开始时，carry 表示此前低位产生的进位，只可能为零或一。分别弹出两个当前数位，某个栈已经空时补零，再累加进 carry。累加后的值暂时表示本位总和，范围为零到十九；对十取余得到本位数字，整除十后才重新成为传给下一轮的进位。

新数位的生成顺序是从低到高，结果却要求从高到低，因此将每个新节点插到当前结果头部。后算出的高位自然排在前面，不需要最终再反转。哑节点 dummy 只提供固定入口，真正结果从 dummy.next 开始。

两个栈都空后也不能立刻结束，还要检查是否留有最高位进位。循环同时覆盖“任一栈非空或进位非零”，就能自动创建需要的额外最高位。

整个过程只读取输入节点值并移动局部游标，不改变任何原节点连接；结果使用新节点构造。

解题步骤

  1. 分别遍历两条输入链表，将数位压入两个栈。
  2. 初始化进位为零，创建结果哑节点。
  3. 两栈或进位仍有内容时，弹出当前位并累加，空栈按零处理。
  4. 用总和余十创建新节点，接到已有结果头部。
  5. 将总和整除十作为新进位，继续处理；最后返回 dummy.next。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<Integer> 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 dummy = new ListNode();

        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            carry += (s1.isEmpty() ? 0 : s1.pop()) + (s2.isEmpty() ? 0 : s2.pop());
            // 头插法：后算出的高位自动排到前面，省掉最后一次反转。
            ListNode node = new ListNode(carry % 10, dummy.next);

            dummy.next = node;
            carry /= 10;
        }

        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    stack1 := []int{}
    stack2 := []int{}
    // 只读不改，出栈顺序即为从个位到最高位。
    for l1 != nil {
        stack1 = append(stack1, l1.Val)
        l1 = l1.Next
    }
    for l2 != nil {
        stack2 = append(stack2, l2.Val)
        l2 = l2.Next
    }

    carry := 0
    dummy := &ListNode{}
    for len(stack1) > 0 || len(stack2) > 0 || carry > 0 {
        if len(stack1) > 0 {
            carry += stack1[len(stack1)-1]
            stack1 = stack1[:len(stack1)-1]
        }
        if len(stack2) > 0 {
            carry += stack2[len(stack2)-1]
            stack2 = stack2[:len(stack2)-1]
        }
        // 头插法：后算出的高位自动排到前面。
        node := &ListNode{Val: carry % 10, Next: dummy.Next}
        dummy.Next = node
        carry /= 10
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(m+n)$，两条链各压栈一次，加法至多处理较长链的位数再加一。
  • 空间复杂度：$O(m+n)$，两个栈保存全部数位；输出的新链表另外需要 $O(\max(m,n)+1)$。

关键点总结

[!green]

  • 栈提供逆序访问，解决输入方向与进位方向不一致的问题。
  • carry 在轮开始和结束时是进位，轮中累加后临时表示当前位总和。
  • 头插让低位先生成、高位后生成仍能得到高位在前的结果。
  • 循环必须覆盖最终进位，短链按高位补零处理。

易错点总结

[!yellow]

  • 从链头直接相加会在低位进位尚未知时就决定高位，计算方向错误。
  • 只在两个栈都非空时循环，会丢掉长链剩余数位。
  • 忽略最后进位，会少生成一个最高位。
  • 头插前新节点要先保存旧结果头，再更新入口；使用保存好的独立指针时则不必机械要求赋值顺序。
  • 不能将任意长度链表转成固定宽度整数，逐位计算才不会丢失高位。

相似题目

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