LeetCode 369. 给单链表加一

约 6 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 5-10 字节跳动 猿辅导 虾皮
标签
数学 链表 加法问题
目录

题目描述

✅ 369. 给单链表加一

image-20220918214816966

题意分析

一个非负整数被拆成一位一位存进单链表，头节点是最高位，每个节点存一个 0 到 9 的数字。要求把这个整数加一，返回加一后的链表头。除了首位为 0 的特例（整数 0 本身），数字不含前导零。

加法天然是从最低位开始的，而最低位在链表尾部；单链表只能沿 next 往后走，拿不到前驱。这个矛盾就是整道题的全部难点，也是它被归为中等而不是简单的原因。常见的三种破解方式是：把链表反转过来做完再反转回去、用栈把节点压进去再弹出、或者不做加法而是直接推理出结果的形态。前两种都要 $O(n)$ 额外操作或空间，第三种能做到一趟扫描加 $O(1)$ 空间。

值域被限死在 0 到 9 是一个很强的信号：加一之后，只有 9 会向前进位，其余数字加一就地结束。而进位一旦发生，被进位的那一位必然从 9 变成 0。这意味着结果的形态其实非常固定，不需要真的模拟逐位相加。

边界要盯住三处：链表全是 9（如 999）时结果位数增加，要在头部新增一个节点；单节点且值为 9；单节点且值为 0（表示整数 0，加一得 1，不能因为「无前导零」的直觉而误判。

解法：寻找最右非 9 节点

核心思路

数字的高位在链表头，而加法从最低位开始；反转链表或借助栈都能获得逆序访问，但其实没有必要。对一个十进制数加一，只会影响“末尾连续的 9”和它前面的那一位：最右侧非 9 数字加一，后面的 9 全部变成 0，更高位保持不变。例如 1299 + 1 = 1300。

因此只需正向扫描，记住最右侧的非 9 节点。扫描过程中每遇到非 9 就覆盖记录，结束后自然得到最后一个；不需要回头找前驱。

全为 9 时不存在这样的原节点，例如 999 + 1 = 1000。在原头前接一个值为 0 的哑节点，并把它作为初始候选，就能统一处理：全 9 时它变成新增的最高位 1；否则它保持 0，返回时跳过即可。

算法不变量是：扫描结束后，notNine 是包含哑节点在内最靠右的非 9 节点，它之后的节点必然全是 9。于是将 notNine 加一不会再次产生进位，而把其后节点全部置 0，正好等价于完整的进位传播。

正确性分两种情况：若原链表存在非 9 节点，最右非 9 之前的前缀不受加一影响，该节点加一终止进位，后缀 9 全变 0；若原链表全是 9，候选始终是哑节点，它从 0 变 1，原节点全变 0。两种情况都得到且只得到原数加一。

解题步骤

  1. 创建 dummy(0) 指向 head，令 notNine = dummy，给全 9 情况预留最高位。
  2. 从头扫描原链表；每当 cur.val != 9，就更新 notNine = cur。
  3. 扫描结束后执行 notNine.val++。它原本不是 9，所以加一后不会继续进位。
  4. 从 notNine.next 开始走到链表尾，将所有节点置 0；由不变量可知它们原来全是 9。
  5. 若 dummy.val == 1，说明原数全为 9，返回 dummy；否则返回 dummy.next，不带前导零。

以 1 → 2 → 9 → 9 为例，扫描后 notNine 指向 2；把它改成 3，再把后面的两个 9 改成 0，得到 1 → 3 → 0 → 0。对于 9 → 9，扫描后候选仍是 dummy；它变成 1，原节点归零，得到 1 → 0 → 0。两类输入走同一套代码。

代码实现

class Solution {
    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode notNine = dummy;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            if (cur.val != 9) {
                notNine = cur;
            }
        }

        // 最右侧非 9 节点加一，其后的 9 全部变成 0。
        notNine.val++;
        for (ListNode cur = notNine.next; cur != null; cur = cur.next) {
            cur.val = 0;
        }
        return dummy.val == 1 ? dummy : dummy.next;
    }
}

func plusOne(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    notNine := dummy
    for cur := head; cur != nil; cur = cur.Next {
        if cur.Val != 9 {
            notNine = cur
        }
    }

    // 最右侧非 9 节点加一，其后的 9 全部变成 0。
    notNine.Val++
    for cur := notNine.Next; cur != nil; cur = cur.Next {
        cur.Val = 0
    }
    if dummy.Val == 1 {
        return dummy
    }
    return dummy.Next
}

复杂度分析

  • 时间复杂度：$O(n)$。第一趟寻找最右非 9 节点，第二趟只将其后的后缀置 0；每个节点至多访问两次。
  • 空间复杂度：$O(1)$。只使用哑节点和若干指针，不使用栈，也不反转链表。

关键点总结

  • 加一的进位只会穿过末尾连续的 9，因此无需真的从后向前遍历链表。
  • 正向遍历时不断覆盖候选，即可得到最右侧满足条件的节点。
  • 哑节点表示最高位前隐含的 0，统一了普通输入和全 9 输入，避免单独创建新头的分支。
  • 能无条件清零后缀，依赖“最右非 9 节点之后全是 9”这条不变量；这是面试时应讲清的正确性依据。

易错点总结

  • 候选初始化为 head 或 null：全 9 输入会产生值为 10 的节点或空指针；应初始化为值为 0 的 dummy。
  • 找到第一个非 9 就停止：需要的是最右非 9。输入 1 → 2 → 9 若停在 1，会错误得到 2 → 0 → 0。
  • 清零从 notNine 自身开始：会把刚完成的加一覆盖掉；必须从 notNine.next 开始。
  • 固定返回 dummy 或 dummy.next：前者会给普通结果添加前导零，后者会让全 9 结果丢失新增最高位。
  • 遗漏单节点边界：0 应变成 1，9 应变成 1 → 0，两者都应由主流程自然处理。

相似题目

题目 难度 考察点
66. 加一 简单 同样的进位规律，但存在数组里可以直接倒序遍历，无需哑节点技巧
2. 两数相加 中等 低位在链表头，顺序天然匹配加法，边遍历边建新链表即可
445. 两数相加 II 中等 高位在头且是两数相加，进位无法预判，必须靠栈或反转来获得逆序访问
415. 字符串相加 简单 字符串可随机访问，双指针从末尾同步左移，是链表加法题的数组版对照
43. 字符串相乘 中等 进位不再局限于末尾一段，必须真正模拟竖式并处理下标错位
67. 二进制求和 简单 换成二进制后每位只有 0 和 1，本题「找最右非 9」的技巧退化为找最右 0
206. 反转链表 简单 反转法方案的前置基本功，也是理解本题为何要绕开反转的参照
面试题 02.05. 链表求和 中等 同时考察低位在前和高位在前两种存储，正好覆盖 2 与 445 的两类处理方式
LCR 025. 两数相加 II 中等 与 445 同题，可直接套用栈或反转的写法