LeetCode 2. 两数相加

约 5 分钟
文章信息 23 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 华为 拼多多 小米 亚马逊 虾皮 携程 LeetCode 热题 100 面试经典 150 题
标签
数学 链表 递归 加法问题
目录

题目描述

✅ 2. 两数相加

image-20220904112618179

image-20220904112624859

题意分析

两个非空链表各自表示一个非负整数，每个节点存一位数字，并且是逆序存放的：头节点是个位，越往后越是高位。要求返回同样逆序表示的和。

「每个节点只存一位」这个设定是最重要的信号。它说明题目考的不是数值运算，而是手工模拟竖式加法：数字被拆散成一位一位，就不能指望语言的整数类型帮忙。加上链表长度没有承诺落在 64 位整数的表示范围内，任何「先拼成整数、相加、再拆回链表」的思路都是不可靠的。

「逆序」这个设定是本题被定为中等而不是困难的原因。竖式加法的进位是从低位流向高位的，而链表只能从头往尾单向遍历——逆序存放恰好让头节点就是个位，从头到尾走一遍，正好按从低位到高位的自然顺序处理每一位，进位顺着遍历方向传下去就行。

需要留意的边界情形：两个链表长度可能不同，短的一方用完之后剩下的位要按 0 参与运算；最高位相加还可能再产生一次进位，此时结果链表比两个输入都长（如 99 + 1 = 100）；两个数都是 0 时结果是单个节点 0，不能返回空链表；答案不允许有多余的前导零，而逆序表示下「前导零」就是链表末尾的零，好在逐位相加的写法天然不会产生它。

解法：逐位相加维护进位

核心思路

模拟竖式加法，同时遍历两个逆序链表。每一位计算：

  • 当前数字：sum % 10
  • 下一位进位：sum / 10

较短链表缺失的位按 0 处理；只要链表还有节点或 carry 不为 0，就继续计算。使用哨兵节点统一结果链表的追加操作。

解题步骤

  1. 创建哨兵节点 dummy，用 tail 指向结果链表尾部。
  2. 将 carry 与两个链表的当前节点值相加；链表为空时跳过。
  3. 追加 sum % 10，并更新 carry = sum / 10。
  4. 两个链表都为空且无进位时结束，返回 dummy.next。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;
        }

        return dummy.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
    carry := 0

    for l1 != nil || l2 != nil || carry != 0 {
        sum := carry
        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        tail.Next = &ListNode{Val: sum % 10}
        tail = tail.Next
        carry = sum / 10
    }

    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(\max(m, n))$，每个节点访问一次。
  • 空间复杂度：$O(1)$，不计返回结果占用的空间。

关键点总结

  • 逆序存储让遍历方向与进位方向一致，一次遍历即可完成。
  • 循环条件必须包含 carry != 0，否则会遗漏最高位进位。
  • 短链表结束后，其当前位按 0 处理。
  • 哨兵节点可以避免单独处理结果链表的头节点。

易错点总结

  • 循环使用 &&，会在较短链表结束时提前退出；这里应使用 ||。
  • 循环条件漏掉 carry，会丢失 5 + 5 产生的最高位 1。
  • 混淆 % 10 与 / 10：前者是当前位，后者是进位。
  • 忘记移动输入指针或 tail，会导致死循环或结果节点被覆盖。
  • 返回 dummy 而不是 dummy.next，结果会多一个占位节点。

相似题目

题目 难度 考察点
445. 两数相加 II 中等 数字改为正序存储，遍历方向与进位方向相反，需要用栈或先反转链表
LCR 025. 两数相加 II 中等 与 445 同题异名，可顺手比较「反转链表」与「用栈」两种顺序翻转手段的取舍
面试题 02.05. 链表求和 中等 主体与本题相同，进阶部分要求同时支持正序存储，适合把两种方向写在一起对比
369. 给单链表加一 中等 加数固定为 1 且链表正序，退化为「找最右侧非 9 的位」，可用哨兵免去扩位判断
415. 字符串相加 简单 载体换成字符串且是正序，改用两个从末尾向前的下标，结果需要最后整体反转
67. 二进制求和 简单 进制由 10 变 2，取余与整除的除数随之变化，验证进位模板与基数无关
66. 加一 简单 数组正序存储且只加 1，绝大多数情况不必新建数组，仅全为 9 时才扩容
989. 数组形式的整数加法 简单 另一个加数是普通整数，可以把它整体塞进 carry，用一个循环同时消化两侧
43. 字符串相乘 中等 从加法升级为乘法，进位可以大于 1，需要用下标错位累加而非单趟扫描