【LC 19】删除链表的倒数第 N 个结点：一趟扫描的关键，是让快指针先出发
适用读者：知道快慢指针能找环，但没想明白为什么「先走 n 步」就能定位倒数第 n 个的人
技术栈：Python 为主，附 Java 版
难度：中等（思路一行字，边界一堆坑）
收获：「间隔锁死」这个一次扫描定位任意倒数位置的思想，以及它为什么能通吃 LC 876、LC 61、面试题 02.02
题目
给你一个链表，删除链表的倒数第
n 个结点，并且返回链表的头结点。要求
一趟扫描实现。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
链表节点的定义（后面所有代码都用它）：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
这道题是 206 反转链表之后，链表双指针的第二块基石。它标着「中等」，但难点根本不在写代码——正解就三行核心逻辑。
难点在于三件事要同时想对：为什么快指针要先走
n+1 步而不是
n 步、为什么要引入哑结点、以及删掉头节点时代码为什么不会崩。
这三件事，每一件都对应一种典型的错误提交。这篇就把它们挨个说透。
一、难在哪：链表不知道自己的长度
数组里删「倒数第 2 个」是 trivial 的：先算
len - 2 是哪个下标，然后把后面的元素前移。因为
数组随时知道自己的长度，
倒数第 k 个 和
正数第 len-k+1 个 之间是一步换算。
链表不行。链表的节点只知道「我的下一个是谁」，整条链有多长，只有从头到尾走完一遍才知道。而且链表删节点也不是「移动元素」，是
改前驱的指针：
删除 4 之前： 3 → 4 → 5
删除 4 之后： 3 ------→ 5
所以删「倒数第 n 个」这个问题，本质上是两个子问题：
- 定位：找到倒数第 n 个节点的前驱（前驱的
next 一改，删除就完成了）；
- 删除：
前驱.next = 前驱.next.next。
第 2 步是一行代码，没有任何悬念。整道题的分量全在第 1 步：
一趟扫描，怎么定位到倒数第 n 个节点的前驱？
二、对照组：两趟扫描怎么解
先把最直觉的写法摆出来，它是一趟扫法的参照物。
def removeNthFromEnd(head, n):
# 第一趟：数出长度 L
length, node = 0, head
while node:
length += 1
node = node.next
# 哑结点：处理「删的就是头节点」
dummy = ListNode(0, head)
node = dummy
for _ in range(length - n): # 走到倒数第 n+1 个（前驱）
node = node.next
node.next = node.next.next
return dummy.next
思路很直白：
倒数第 n 个 =
正数第 L-n+1 个，它的前驱是
正数第 L-n 个，从哑结点走
L-n 步就到了。逻辑完全正确，复杂度也还是 O(n)。
但题目要求
一趟扫描。两趟扫法的问题不在于「慢」，而在于它把「定位」拆成了两次遍历：先量长度，再按换算公式走。
一趟扫法的全部魔法，就是让这两个动作同时发生。
先记住两趟扫法里的两个要素，等下一趟扫法会原样用到：
- 删除靠的是前驱，不是待删节点本身；
- 哑结点让「删头」不再需要特判——没有它，
[1], n=1 这种输入就得单独写 if。
三、一趟扫描：把间隔锁死
3.1 核心想法
一个生活化的比喻：一条长队里想知道「离队尾还有 5 个人」的位置在哪，你不用先数全队多少人。
让两个人保持 5 个人的间距一起往队尾走，前面那个人踩到队尾的那一刻，后面那个人站的位置就是目标。
翻译成指针语言：
fast 和 slow 都从哑结点出发；fast 先走 n+1 步——此刻两者的间距是 n+1；- 然后两个指针同步前进，一步一格；
fast 走出链表（变成 null）的那一瞬间，slow 停的位置恰好是倒数第 n+1 个节点——也就是待删节点的前驱。
为什么间距是
n+1 不是
n？因为我们要停在前驱上。
fast 比
slow 多走
n+1 步，同步前进时
slow 始终落后
fast n+1 个位置；
fast 落到
null（所有 L 个节点之后），
slow 就落在倒数第
n+1 个上，它的
next 正是倒数第
n 个。
一句话总结这个技巧：
先走的指针负责探路，后走的指针负责定位；间距锁死多少，定位就差多少。
3.2 为什么能保证同步结束时刚好到位
用下标验证一遍（0 从哑结点数起，节点
1~L）：
fast 先走 n+1 步，停在节点 n+1（值上就是第 n+1 个节点）；- 两者间距
n+1，同步前进时永远不变——这是整个算法的不变量；
fast 从节点 n+1 走到 null 还需要 L-n 步（n = L 时这个数为 0——fast 在先走阶段就已落到 null，slow 不动，正好是删头的情形）；- 同步移动了
L-n 步，slow 从哑结点走到节点 L-n；
- 节点
L-n 的倒数编号：它后面还有 n 个节点（L-n+1 到 L），所以它正是倒数第 n+1 个。✓
拿演示用例核对：
L=5, n=2。
fast 先走 3 步停在节点
3，同步走
5-2=3 步，
slow 停在节点
3（值 3）——它后面还有
4、5 两个节点，倒数第 3 个，正是节点
4 的前驱。删除后得到
[1,2,3,5]。✓
「间距不变」是这个算法唯一的不变量。 面试时能主动说出「这里有个循环不变量」，比多写出十行代码更能证明你是理解的。
四、哑结点：把「删头」变成普通情况
4.1 没有 dummy 会发生什么
先看不加哑结点的版本会多出什么：
def removeNthFromEnd(head, n):
fast = head
for _ in range(n):
fast = fast.next
if fast is None: # ⚠️ 特判：n 等于链表长度，删的是头节点
return head.next
slow = head
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
head = [1,2], n = 2 走一遍：
fast 先走 2 步直接冲出链表变成
None。此时要删的正是头节点自己——
头节点没有前驱，head 已经是它自己的「前驱」了，只能单独
return head.next。
这就是头节点删除的经典尴尬：普通节点的删除靠前驱，头节点的前驱不存在。
4.2 dummy 的作用：凭空造一个前驱
dummy = ListNode(0, head)
在头节点前面垫一个不存数据的哑结点，链表变成：
dummy → 1 → 2 → 3 → 4 → 5 → ∅
原来的头节点
1 有了前驱，
「删头」和「删中间」从此是同一种操作：都停在前驱、改一个
next。而且
fast 从
dummy 出发走
n+1 步，即使
n 等于链表长度（要删的正是头节点），
fast 也只是恰好落到
null——不会越界报错，同步阶段一步不走，
slow 原地留在
dummy 上，第 ④ 行就把
dummy.next 从
1 改成了
2。特判整个消失。
这是链表题里 dummy 出场的第二条经典理由（第一条在 LC 25 里：头节点可能被换掉时需要一个固定锚点）。
只要操作可能落在头节点上，就先垫一个 dummy。
五、动画：看着两个指针把 4 挤出去
下面这个动画把
[1,2,3,4,5]、
n=2 的完整过程拆成了 9 步。留意三件事：
- 先走的 3 步：
fast 独自前进，拉开 n+1 = 3 的间隔，slow 原地不动；
- 间隔线：同步阶段那条「间隔 3」的标注始终不变——这就是循环不变量；
- 最后一步：
3 的箭头从指向 4 变成跨过 4 直指 5，被删节点变灰，但它还挂在内存里——链表题里「删除」从来不是销毁节点，只是没人再引用它。
看完动画可以注意一个细节：
fast 探路时走过的节点数（
n+1）加同步阶段走过的步数（
L-n），恰好等于
L+1——从
dummy 到
null 的全程。
没有任何节点被访问两次，这就是「一趟」的含义。
六、代码逐行拆解
6.1 Python
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # ① fast 先走 n+1 步
fast = fast.next
slow = dummy # ② slow 从 dummy 出发
while fast: # ③ 两个指针同步前进
fast = fast.next
slow = slow.next
slow.next = slow.next.next # ④ slow 停在前驱上，摘掉目标节点
return dummy.next # ⑤ 返回 dummy.next，而不是 head
for _ in range(n + 1)（①） —— 注意是
n+1。
fast 要走到「倒数第 n 个的后一个位置」，这样同步结束时
slow 才停在前驱上。写成
range(n) 是本题最高频的错误，后果见第七节。
slow = dummy（②） —— 从哑结点出发，不是
head。
slow 的初始位置就是「倒数第 L+1 个」（虚拟的头节点前驱），间距由此锁死为
n+1。
while fast（③） —— 循环条件是
fast 本身，不是
fast.next。因为
fast 先走的那段已经把「停在前驱」的偏差吃掉了，这里让它一路走到
null 即可。（如果 ① 里只走
n 步，这里就得写
while fast.next，两种约定别混用。）
slow.next = slow.next.next（④） —— 真正的删除。此时
slow 是倒数第 n+1 个节点，
slow.next 是倒数第 n 个，跳过它即可。Python 有垃圾回收，被摘下的节点自动回收；Java 交给 GC；C/C++ 才需要手动
free。
return dummy.next（⑤） ——
必须返回 dummy.next，不是 head。当
n 等于链表长度时，头节点被删掉了，
head 指向的节点已经不在链上，返回它就是返回了被删除的垃圾。这是第二个高频错误。
6.2 完整推演表
head = [1,2,3,4,5]，
n = 2，
L = 5：
同步阶段的
slow 落点
3，正是节点
4（倒数第 2 个）的前驱。
6.3 Java 版
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
ListNode fast = dummy;
for (int i = 0; i < n + 1; i++) { // ① 先走 n+1 步
fast = fast.next;
}
ListNode slow = dummy;
while (fast != null) { // ③ 同步前进
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next; // ④ 删除
return dummy.next; // ⑤ 注意不是 head
}
}
七、边界情况
三个边界
没有一个需要 if——哑结点 +
n+1 这套约定把它们全部吸收了。如果发现有边界开始需要特判，多半是这两个约定有一个没设对，回头查比打补丁划算。
题目保证了
1 ≤ n ≤ 链表长度，所以
fast 先走的
n+1 步最多正好落到
null，不会越界。如果面试官放开这个限制（
n 可能比链表还长），① 的循环里就要检查
fast 是否提前变
null，直接返回原链表。
八、复杂度
时间都是 O(L)，两趟加起来每个节点也只被访问常数次。
一趟解法的价值不在更快，而在「只对数据流过一遍」——这个模式能推广到所有「不知道总长度、但想知道倒数第 k 个」的场景：比如只允许顺序读一遍的日志文件、数据流里的倒数第 k 条记录。那种时候「先量长度」根本不成立，间隔锁死是唯一解法。
九、常见坑
按踩到的频率排序：
1. fast 先走了 n 步而不是 n+1 步，又没改循环条件
for _ in range(n): # 只走 n 步
fast = fast.next
...
while fast.next: # 如果这里还是 while fast，slow 会停在待删节点上
fast = fast.next
slow = slow.next
slow.next = slow.next.next # ❌ 删掉的是「倒数第 n+1 个」，方向反了
两种约定都能写出正确代码——「先走 n 步 +
while fast.next」或「先走 n+1 步 +
while fast」——但
不能混着来。混用的结果是慢指针差一个身位，删错节点。
2. 返回 head 而不是 dummy.next
删头节点的用例（
[1,2], n=2）会当场挂掉：返回了一个已经不在链上的节点。
3. 不加 dummy，删头时忘记特判 if fast is None
[1], n=1 或
[1,2], n=2 直接空指针异常。
4. 把「删除」理解成销毁节点
slow.next = slow.next.next 之后，被删节点的
next 依然指着链表里的节点。在 C/C++ 里这意味着内存泄漏，也意味着某些 OJ 的「断环检测」会误报。严谨的做法是把被删节点的
next 置空。
5. 先走阶段没有考虑 n+1 可能正好等于链长加一
题目保证了
n ≤ L，
fast 最多走到
null 就停；但如果面试变体放开了这个约束，
for 循环里的
fast.next 会抛空指针。
「题目保证的约束写在哪，防御性检查就该省在哪」——但要能说出来，而不是碰巧没写。
十、面试怎么答
- 先复述定位思路：「删除靠前驱，所以目标是倒数第 n+1 个节点。」
- 说核心技巧：「快慢指针间隔锁死为 n+1：fast 先走 n+1 步，然后同步前进，fast 到 null 时 slow 正好停在前驱上。」
- 主动提哑结点：「引入 dummy 是为了把『删头』变成普通删除，返回值也统一成 dummy.next。」
- 报复杂度：「一趟扫描，时间 O(L)，空间 O(1)。」
- 抛出追问：「同一套『间隔锁死』还能解决：LC 876 找中点（fast 一次两格，slow 一次一格）、LC 61 旋转链表（定位倒数第 k 个再把尾部接到头部）、面试题 02.02 返回倒数第 k 个节点——要展开吗？」
第 5 步的潜台词：快慢指针不是一个 trick，是一个
家族。
结语
把快慢指针家族放在一张表里：
变化的是步频和初速度，不变的是「让两个指针产生可控的相对运动，用其中一个探测，用另一个定位」。
所以下次遇到「倒数第 k 个」类的题目，先别想数长度。问自己两个问题：
- 我需要定位的是倒数第几个？（要删除就要多退一步，找前驱）
- 两个指针的间隔和步频怎么设，才能让探测的那个刚好停在我要的位置？
把间隔当成一次性的初始条件锁死，剩下的就是同步前进——这比任何换算公式都稳。
本文的推演动画是页面里的交互组件，可以单步回放。如果想自己验证间隔逻辑，拿纸画六个格子（最左画个 dummy）摆两枚硬币就行——在纸上推一遍，胜过看十遍代码。