LeetCode LCR 021. 删除链表的倒数第 N 个结点

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 3 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 021. 删除链表的倒数第 N 个结点

题意分析

给定单链表的头节点 head 和整数 n，删除从末尾数起的第 n 个节点，返回删除后的头节点。

单链表只能沿 next 往后走，既拿不到长度，也拿不到前驱。而删除一个节点真正需要的东西是它的前驱——只有握住前驱，才能执行「跳过」这一步。所以题目问的是「倒数第 n 个节点」，我们要找的却是「倒数第 n+1 个节点」，这个错位是本题的第一层信息。

进阶要求「只遍历一次」，这条约束直接否决了「先数长度、再走一遍」的两趟做法，逼着我们在同一趟里同时维护两个位置，用它们之间的相对距离替代绝对长度。

题目保证 1 <= n <= 链表长度，所以不需要处理 n 越界。但 n 恰好等于链表长度时删的是头节点，返回值不再是原 head，这说明代码里需要一个「不会因为删除而失效的锚点」。

边界还包括：链表只有一个节点且 n = 1，删完是空链表，必须返回空而不是崩掉。

解法：双指针收缩边界

核心思路

先看暴力：遍历一遍数出长度 L，再从头走 L - n 步落到前驱上，改一次指针即可。这个做法正确，但要走两趟，且瓶颈很明确——「倒数」这个信息只有走到尾部才揭晓，第一趟纯粹是为了把它换算成「正数第几个」。

换个角度观察：倒数第 n 个节点的本质，是它到尾节点的距离恒为 n - 1。这个距离是常量，与总长度无关。于是只要有两个指针始终保持固定间距，当靠后的那个抵达尾部时，靠前的那个自动落在我们要的位置上，完全不需要先知道 L。

由此确定循环不变量：进入第二个循环后的任意时刻，从 slow 出发走 n 步恰好到达 fast。初始化时先让 fast 单独前进 n 步就建立了这个不变量；此后两个指针同速推进，间距自然被保持。当 fast.next == null（fast 是尾节点）时，slow 距尾节点 n 步，也就是倒数第 n + 1 个位置——正是待删节点的前驱。

剩下的问题是删头。n 等于链表长度时前驱不存在，代码就得分支特判。解决办法是在 head 前面挂一个哑结点 dummy，让 slow 从 dummy 起步：此时「倒数第 n + 1 个位置」在最坏情况下就是 dummy 本身，前驱永远存在，删头和删中间合并成同一条代码路径。最后返回 dummy.next 而不是 head，因为 head 可能已经被删掉了。

解题步骤

建哑结点：dummy = new ListNode(0, head)，fast 与 slow 都从 dummy 出发。之所以两者都从 dummy 起步而不是从 head 起步，是为了让「间距 n」这个不变量与「slow 停在前驱上」这个目标严丝合缝地对上；如果两者都从 head 起步，slow 最后会停在待删节点自身，删不掉。

拉开间距：while (n-- > 0) fast = fast.next;，让 fast 单独走 n 步。这一步建立不变量，是后面所有推理的前提。因为题目保证 n 不超过链表长度，这里不会走出界。

同速推进：while (fast.next != null) { slow = slow.next; fast = fast.next; }。循环条件必须是 fast.next != null 而不是 fast != null——前者停在尾节点，后者会多走一步停到空，slow 随之多走一步落到待删节点身上。

摘除节点：slow.next = slow.next.next，把待删节点从链上跳过去。单链表删除只需要改前驱的一根指针，不需要动待删节点本身。

返回 dummy.next：不能返回 head。n 等于链表长度时 head 就是被删的那个节点，返回它会把已删节点又带回来。

以 1 → 2 → 3 → 4 → 5、n = 2 走一遍。链表实际形态是 dummy → 1 → 2 → 3 → 4 → 5 → null，两个指针都从 dummy 起步。第一个循环让 fast 走 2 步，落到节点 2，此时 slow 仍在 dummy，间距为 2。进入第二个循环：fast 在 2、slow 在 dummy，fast.next 是 3 非空，推进后 slow 到 1、fast 到 3；fast.next 是 4 非空，推进后 slow 到 2、fast 到 4；fast.next 是 5 非空，推进后 slow 到 3、fast 到 5；此时 fast.next 为空，循环退出。slow 停在节点 3，slow.next 是节点 4，正是倒数第 2 个，执行 3.next = 5 得到 1 → 2 → 3 → 5，返回 dummy.next 即节点 1。

再看极端用例 1、n = 1：fast 走 1 步落到节点 1，slow 在 dummy；fast.next 为空，第二个循环一次都不进；slow.next = slow.next.next 即 dummy.next = null，返回 dummy.next 为空链表，结果正确且没有用到任何特判——这正是哑结点带来的收益。

代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 哑结点让「删头」与「删中间」走同一条路径。
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        // 停在尾节点时，slow 距尾 n 步，即待删节点的前驱。
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 哑结点让「删头」与「删中间」走同一条路径。
    dummy := &ListNode{0, head}
    fast := dummy
    slow := dummy
    for n > 0 {
        fast = fast.Next
        n -= 1
    }
    // 停在尾节点时，slow 距尾 n 步，即待删节点的前驱。
    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}

复杂度分析

时间复杂度：$O(L)$，L 为链表长度。fast 从头走到尾恰好一趟，slow 走的步数不超过 fast，循环体内全是常数操作，总共只扫描了一遍链表。

空间复杂度：$O(1)$，只额外用了 dummy、fast、slow 三个引用，与链表长度无关；没有开数组，也没有递归栈。

关键点总结

「倒数第 k 个」等价于「与尾部保持固定间距」，把绝对位置换成相对距离，就能在不知道总长度的前提下一趟定位——这是快慢指针类题目的通用迁移点。

删除操作需要的是前驱而不是目标节点本身，先想清楚「我要停在哪」再决定指针怎么初始化。

哑结点的价值是把「头节点会变」这类边界吸收进主逻辑，任何返回值可能不是原 head 的链表题都值得先加一个。

循环条件写 fast.next != null 还是 fast != null，直接决定 slow 落点差一位，这类差一错误要靠画图或代入最小用例确认，不能凭感觉。

面试视角：面试官往往先接受两趟解法，再追问「能不能一趟」。此时要主动讲出「保持间距 n」这个不变量，并说明哑结点为什么让 n = L 不再是特例；能顺带指出「题目保证 n 合法，否则拉开间距那一步要判空」，会显得边界意识完整。

易错点总结

两个指针都从 head 起步：1 → 2、n = 2 时 fast 走 2 步已越过链尾变成空，fast.next 直接空指针异常。

只有 slow 从 dummy 起步而 fast 从 head 起步：间距凭空少了 1，1 → 2 → 3 → 4 → 5、n = 2 会删掉节点 5 而不是节点 4。

循环条件写成 fast != null：同样是 n = 2 的用例，slow 会多走一步停在节点 4，slow.next = slow.next.next 删掉的是节点 5，答案错位一个。

返回 head 而不是 dummy.next：1 → 2、n = 2 时应返回 2，返回 head 会把已删除的节点 1 当成头，输出 1 → 2。

拉开间距时写成 while (n-- >= 0) 或多走一步：1 → 2 → 3、n = 3 时 fast 会走到空，后续 fast.next 抛空指针异常。

忘记 dummy 直接特判删头：写成 if (n == 链表长度) return head.next; 就必须先求长度，与「一趟遍历」的进阶要求自相矛盾，白写了双指针。

删除时写成 slow = slow.next.next：只是把局部变量往后挪，原链表一根指针都没改，返回结果与输入完全一致。

Go 里写 dummy := &ListNode{Next: head} 后返回 head：与 Java 版同样的返回值错误，n 等于长度时结果多出一个已删节点。

相似题目

题目	难度	考察点
19. 删除链表的倒数第 N 个结点	中等	与本题同题，可直接套用哑结点 + 固定间距的写法
876. 链表的中间结点	简单	间距不再固定，改成一慢一快按 1:2 速度推进来定位中点
剑指 Offer 22. 链表中倒数第k个节点	简单	只需返回倒数第 k 个节点本身，停在目标而非前驱，无需哑结点
面试题 02.02. 返回倒数第 k 个节点	简单	只要返回节点值，连指针改动都不涉及，是本题定位逻辑的最小内核
61. 旋转链表	中等	同样要找倒数第 k 个前驱，但 k 需先对长度取模，且要成环再断开
82. 删除排序链表中的重复元素 II	中等	删除条件从「位置」变成「值重复」，前驱要停住不动直到跳过整段