LeetCode 445. 两数相加 II

约 6 分钟
文章信息 19 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 字节跳动 美团 阿里巴巴 快手 腾讯 猿辅导 百度 华为 拼多多 网易 亚马逊 虾皮 作业帮
标签
数学 栈 链表 加法问题
目录

题目描述

✅ 445. 两数相加 II

image-20230305195919912

image-20230305195925331

题意分析

给两个非空链表，各自表示一个非负整数，每个节点存一位数字，且最高位在链表头部。要求把两数相加，返回一个同样以最高位在前的链表。

「高位在前」是本题与 2 题最本质的差别，也是全部难度来源。竖式加法必须从最低位开始算，因为进位只能从低位向高位传播；而链表只能从头往尾单向走，头部恰好是最高位，等于走的方向和算的方向正好相反。题目给的两条链表长度还可能不等，[7,2,4,3] 与 [5,6,4] 对齐时要靠右对齐而不是左对齐，这也说明不能拿两个指针一起从头往后逐位配对相加。

进阶要求写得很明确：不能翻转输入链表。这条约束把「先把两条链表原地反转，退化成 2 题，算完再反转回来」这条最省事的路堵死了，逼你换一种方式拿到「低位优先」的访问顺序。面试时这条几乎一定会被强调，答题前要先确认清楚是否允许修改输入。

边界上要盯住三处：最高位相加后可能再产生一次进位，例如 [5] 加 [5] 的结果是 [1,0]，位数比两个输入都长，所以结果长度是 max(m, n) 或 max(m, n) + 1；两链表长度不等时，短的那条算完后长的那条还得带着进位继续走；单个数字可能是 [0]，相加结果为 [0] 而不是空链表。

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

核心思路

问题关键：链表从高位指向低位，但竖式加法必须从低位开始，因为进位向高位传播；题目又不允许反转输入链表。把整条链表转成整数会溢出，也绕开了按位加法的考点。

为什么选栈：顺序压入、逆序弹出，正好能在不改指针的前提下先取最低位。每算出一位，再把新节点插到结果头部；计算顺序虽是低位到高位，最终链表仍会变成高位在前。

不变量：每轮开始时，两个栈顶是各自尚未处理的最低位，carry 是低一位传来的进位，head 是已处理各位组成的正确高位在前链表。弹出存在的数字并加上 carry 后，sum % 10 是当前位，sum / 10 是新进位；将当前位头插即可继续保持不变量。

正确性：每轮按竖式规则得到当前位和下一位进位，并通过头插保持结果顺序。两个栈都空且 carry == 0 时，所有位和最终进位都已处理，因此 head 就是完整答案。若允许修改输入，可反转两条链表来降低辅助空间，但不符合本题进阶要求。

解题步骤

  1. 分别遍历两条链表，把节点值压入两个栈，全程不修改输入。
  2. 初始化 carry = 0、head = null；只要任一栈非空或仍有进位，就继续计算。
  3. 每轮以 carry 为初值，两个栈非空时分别弹出一位相加；短链耗尽后等价于在高位补零。
  4. 用 sum % 10 创建节点并头插到 head 前，再令 carry = sum / 10。
  5. 循环结束返回 head。

口述样例：7243 + 564 依次算出低位 7、0、8、7，每次头插后结果依次为 [7]、[0,7]、[8,0,7]、[7,8,0,7]。

代码实现

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)$。两条链表各入栈一次，加法阶段每一位再出栈一次。
  • 空间复杂度：$O(m + n)$。两个栈保存全部数字；返回链表不计入额外空间。

关键点总结

  • 栈解决“链表访问方向”和“加法计算方向”相反的问题，头插解决“计算顺序”和“结果顺序”相反的问题。
  • 循环条件必须包含 carry != 0，否则会漏掉新增的最高位。
  • 两个栈用“非空才弹出”自然处理长度差，无需显式补零或先对齐。
  • 面试追问 $O(1)$ 辅助空间时，应先确认是否允许反转并恢复输入链表；禁止修改输入时，线性栈空间是合理代价。

易错点总结

  • 循环条件写成“两栈都非空”：[7,2,4,3] + [5,6,4] 会漏掉长链剩余的最高位。
  • 漏掉最终进位：[5] + [5] 会得到 [0] 而不是 [1,0]。
  • 使用尾插：数字按低位到高位产生，尾插会得到正确结果的逆序。
  • 头插顺序写反：必须先让新节点指向旧 head，再更新 head，否则可能形成自环或断链。
  • 直接从两个链表头逐位相加：长度不等时会按左侧对齐，而数字应按最低位对齐。
  • 将链表拼成 long：链表可表示的数字远超整数范围，必然存在溢出风险。

相似题目

题目 难度 考察点
2. 两数相加 中等 低位在前，可直接同步遍历尾插，无需栈
369. 给单链表加一 中等 高位在前的加一，可用「最后一个非 9 位」技巧免栈
LCR 025. 两数相加 II 中等 本题的 LCR 版本，同样带不修改输入的进阶要求
面试题 02.05. 链表求和 中等 同一题的两种存储顺序都要求实现，正反序各写一遍