LeetCode 369. 给单链表加一

2025-11-13 HGNULB 约 4 分钟

文章信息 10 个分类 2 个标签

分类

LeetCode CodeTop 中等已解决需复习会员题 5-10 字节虾皮猿辅导

题目描述

✅ 369. 给单链表加一

给定一个非空单链表的头节点 head，链表表示一个非负整数，每个节点保存一位数字，最高位位于链表头部。请将这个整数加一，并返回结果链表的头节点。

示例 1：

输入：head = [1,2,3]
输出：[1,2,4]

示例 2：

输入：head = [0]
输出：[1]

提示：

链表中的节点数目在范围 [1, 100] 内。
0 <= Node.val <= 9。
链表表示的整数不包含前导零，数字 0 本身除外。

题意分析

非空单链表按从高位到低位保存一个非负整数，每个节点是一位数字。将这个数加一，返回结果链表；如果原数全为 9，结果需要多一个最高位。

解法：寻找最右非 9 节点

核心思路

[!blue]

加一从最低位开始：遇到 9 就变成 0 并继续进位，遇到小于 9 的数字则加一并停止。因此只需修改末尾连续的 9，以及它们前面的那个非 9 节点，其余高位保持不变。

单链表无法直接向前回溯，但可以正向扫描，始终用 notNine 记住最近遇到的非 9 节点。扫描结束时，它就是最右侧非 9 节点，后面的所有节点必然都是 9；让它加一，再把后缀清零，就完成了同样的进位过程。

为了让全 9 输入也有进位停止的位置，在头前接一个值为 0 的哑节点 dummy，并用它初始化 notNine。原链表存在非 9 节点时，哑节点保持为 0，返回原头；否则哑节点变为 1，作为新增最高位返回。尾节点本身不是 9 时，待清零的后缀为空，同一流程也适用。

解题步骤

创建 dummy(0) 指向 head，令 notNine = dummy，给全 9 情况预留最高位。

从头扫描原链表；每当 cur.val != 9，就更新 notNine = cur。

扫描结束后执行 notNine.val++。它原本不是 9，所以加一后不会继续进位。

从 notNine.next 开始走到链表尾，将所有节点置 0；由不变量可知它们原来全是 9。

若 dummy.val == 1，说明原数全为 9，返回 dummy；否则返回 dummy.next，不带前导零。

代码实现

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)$，其中 n 为节点数。第一趟寻找最右非 9 节点，第二趟只将其后的后缀置 0，每个节点至多访问两次。

空间复杂度：$O(1)$。只使用哑节点和若干指针，不使用栈，也不反转链表。

关键点总结

[!green]

加一的进位只会穿过末尾连续的 9，因此无需真的从后向前遍历链表。

正向遍历时不断覆盖候选，即可得到最右侧满足条件的节点。

哑节点表示最高位前隐含的 0，统一了普通输入和全 9 输入，避免单独创建新头的分支。

易错点总结

[!yellow]

notNine 要初始化为值为 0 的哑节点，否则全 9 输入找不到合法的进位终点。

不能遇到第一个非 9 就停止，必须持续更新到最右侧，才不会改动本应保留的高位。

清零从 notNine.next 开始，不能覆盖刚完成加一的节点。

返回时根据 dummy.val 判断是否新增最高位，不能固定返回哑节点或原头。

不要把整个链表转成固定宽度整数，题目允许最多 100 位，可能超出整数范围。

相似题目

题目	难度	关联与区别
66. 加一	简单	逐位加一及进位规则相同，数组能从末尾读取，本题链表要借助反转、递归或最后一个非9节点。
445. 两数相加 II	中等	同样处理高位在前的链表加法，本题第二个加数固定为1。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2025/62581654

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！