单链表删除倒数第N个节点：双指针与虚拟头结点的核心细节

1. 题目拆解：先搞清楚“倒数第N个”到底怎么定位

1.1 题目结构与基本要求

LeetBook 乐扣题库里的第 19 题，题目原文非常短：给你一个单链表，删除链表的倒数第 n 个结点，返回链表的头结点。结点的定义只有 val 和 next 两个字段，没有 prev 指针，没有哨兵头结点，传入的 head 就是链表的第一个有效结点。

这道题能长期霸榜高频题，是因为它把链表操作的几个核心考点一次性塞进来了：遍历计数、指针相对位置、边界条件、删除操作必须基于“前驱结点”。面试官考这道题，表面看是考你会不会写循环，实际上是看你能不能回答清楚一个问题：在只知道 next 指针的单向链表里，要删除一个结点，必须找到它前面那个结点，让前一个结点的 next 跨过它指向后面。如果一上来就把整个链表转成数组或者塞进额外的容器里，虽然也能过判题，但基本等于告诉面试官，你对链表底层操作没有手感。

很多刚开始刷题的同学会不自觉地把“删除倒数第 n 个结点”想成“找到倒数第 n 个结点”，这两个目标之间正好差了一个身位。找到目标节点只需要确认它的位置，删除目标节点却需要操作它前一个结点的 next 指针。这个微妙的偏差，正是这道题最核心的门槛。

1.2 链表题与数组题的思维差异

数组允许你用下标随机访问任意位置，arr[i] 说来就来，顺序和逆序都随心所欲。链表是单方向的，你只能从 head 出发，一个 next 一个 next 往下走，想退回上一步？没有 prev 指针，只能从头再走。这就是单链表最反直觉的地方：你不知道某一个结点在前还是在后，除非你真正走到它面前。

所以链表题有一个默认的命题环境：“如果只能遍历一次，我能不能拿到足够的信息？”答案通常是能，但需要一点技巧，而双指针就是这类技巧的典型代表。再加上删除操作本身要求“前驱”，两个难点叠在一起，构成了第 19 题的全貌。

我给同事讲这道题时喜欢用一个类比：一列单行队伍，每个人只知道身后那个人是谁，你不能回头，只能往前走。现在要求“把从后往前数第 n 个人请出队伍”，但你不知道队伍总共有多少人。最笨的办法是你先走到队尾数清人数，再回到目标前一个人那里做操作。双指针的玩法则是：让一个“快指针”先提前出发走 n 步，然后另一个“慢指针”和它保持同步往前走。当快指针碰到队尾时，慢指针停下的位置恰好就是目标前一个人。这个画面要是能在大脑里成形，代码写出来就是顺水推舟的事。

2. 三种思路的对比：从暴力到双指针

2.1 两次遍历：先求长度，再删节点

最容易理解，也最能保证正确性的，当然是两次遍历。第一次从头走到尾，数出链表长度 L，那么倒数第 n 个结点等价于正数第 L - n + 1 个结点。第二次遍历，走到第 L - n 个结点，修改它的 next 指向，跳过目标，删除完成。

这段代码写出来大约只有十行，时间 O(L)，空间 O(1)。唯一的劣势是链表会被扫两遍。但我建议你在面试里不要上来就否定这个方案，更不要一开口就背双指针模板。更好的表达顺序是：先说“最直接的思路是两次遍历，先统计长度，再走 L-n 步找到前驱”，然后补一句“但这会扫描两遍，有没有可能一遍完成”。一次递进，既展示了基础思维，又展示了优化意识。很多人忽略了这个过程，反而显得像是在背题。

两次遍历里最容易踩的坑是循环次数。链表 [1,2,3,4,5]，n=2，目标删除 4，前驱是 3。正数第 3 个结点的下标正好是 L - n = 3，所以第二次循环要走 3 步。如果你写成 for (int i = 1; i < L - n + 1; i++)，也很容易在边界上多走或少走一步。我的习惯是直接用 while 循环配合计数器，每走一步先想清楚“现在 head 指向的是不是我想停的位置”，再决定是否继续。

2.2 双指针一次遍历：快慢指针拉开距离

双指针的思路是让两个指针一开始指向同一个起点，快指针先额外走 n 步，让两个指针之间保持长度为 n 的“档距”。之后两个指针以相同速度同步前进，当快指针到达链表末尾时，慢指针正好落在我们关心的位置。这个“关心的位置”到底是目标结点本身，还是目标结点的前驱，取决于快指针先走 n 步还是 n+1 步，也取决于 while 循环的判断条件。这两处细节，是双指针写法里最容易打架的地方。

先看快指针走 n 步的情况。快慢指针都从 dummy 出发时，快指针先走 n 步后到达 n 号位置。如果此时让两个指针同步移动，直到快指针停在 null，慢指针会落在正数第 L - n + 1 号位置，也就是目标结点本身。要删除目标，就得额外用一个 prev 记录慢指针的前一个位置，否则删不掉。

再看快指针走 n+1 步的情况。快指针先走 n+1 步，让距离拉开到 n+1，然后同步移动直到快指针遇到 null。由于多走了一步的偏移，慢指针最终停在第 L - n 号位置，也就是目标结点的前驱。这个时候执行 slow.next = slow.next.next，恰好把目标跳过去。这个版本最干净，也是我推荐的写法。

你可能已经发现：只要把“偏移量”和“循环终止条件”看作一组配套参数，就不会混乱。快指针先走 n 步、循环条件是 fast.next != null，效果和先走 n+1 步、循环条件是 fast != null 几乎一样——慢指针都会落在前驱。不同的组合之间没有对错，只有能不能一眼看明白。

2.3 虚拟头结点到底解决了什么问题

虚拟头结点，也就是 dummy node，是在真实链表头部之前额外挂一个不存储业务数据的哨兵结点。它的最大价值是让“删除头结点”变成和删除普通结点一样的操作。没有 dummy 时，如果要删除的结点恰好是 head，你必须单独处理：要么返回 head.next，要么在外部修改头指针。有了 dummy，一切都变成了同一个模式：dummy.next 始终指向真正的链表头，最终返回 dummy.next 即可。

刚开始写链表的人最容易在“删除头结点”上翻车。比如链表只有一个结点 [1]，n=1，删除后应该返回空链表。如果不用 dummy，代码必须显式判断是否需要更新头指针。逻辑不多，但分支一多，人就容易漏。面试时你主动提出加一个 dummy，面试官通常很受用，因为这代表你提前考虑过边界情况。

当然也要注意，dummy 毕竟是辅助变量，最终一定要返回 dummy.next，而不是 dummy 本身。我帮人 review 代码时见过好几次这种低级错误：判断逻辑全对，结果返回值带了个哨兵结点，输出看起来多了一个 null 或者 0，排查半天才发现是这里的问题。

3. 双指针实现的完整细节与代码注释

3.1 标准实现与每一步的意图

下面这段是我最推荐的主代码，用 Java 写，每行的意图我都注释出来：

public ListNode removeNthFromEnd(ListNode head, int n) { // 哨兵结点：把删除头结点的特殊情况统一为普通删除 ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; // 快指针先走 n+1 步 // 为什么是 n+1 而不是 n？ // 因为慢指针最终要落在目标结点的前驱上 for (int i = 0; i <= n; i++) { fast = fast.next; } // fast 和 slow 同步前进，直到 fast 走到链表末尾的 null while (fast != null) { fast = fast.next; slow = slow.next; } // 此时 slow.next 就是要删除的结点 slow.next = slow.next.next; return dummy.next; }

核心就是for (int i = 0; i <= n; i++)这个循环里的<=。真正的意思是执行了 n+1 次循环。如果写成< n，最后 slow 会落在目标本体上，删除语句就会变成跳过目标的下一个结点，题意完全跑偏。

如果实在不习惯 n+1，也可以用“快指针先走 n 步，while (fast.next != null) 作为循环条件”的变体。由于 fast 停在最后一个有效结点而不是 null，变相少走了一步，slow 同样落在前驱。两种写法都能通过，但我个人觉得 n+1 配while (fast != null)的思路更直观，判断条件统一，不容易在边界上多想一步。

Python 版本几乎可以直接平移：

def remove_nth_from_end(head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) fast = slow = dummy for _ in range(n + 1): fast = fast.next while fast: fast = fast.next slow = slow.next slow.next = slow.next.next return dummy.next

3.2 为什么 slow 最终会落在“前驱”上

为了不留死角，我用一个具体例子把指针移动的全过程摆出来。假设链表为 1 -> 2 -> 3 -> 4 -> 5，n = 2，目标删除倒数第 2 个结点，也就是 4。

初始状态：dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null。fast 和 slow 都指向 dummy。

快指针走 n+1 = 3 步：dummy -> 1 -> 2 -> 3，此时 fast 指向结点 3，slow 还在 dummy。两指针之间隔了 3 个位置。

接着同步移动：fast 从 3 走到 null，需要经历 3 -> 4 -> 5 -> null，总共 3 步。slow 同样走 3 步：dummy -> 1 -> 2 -> 3，最终停在结点 3。结点 3 正是目标 4 的前驱。执行 slow.next = slow.next.next，把 3 的 next 从 4 改成 5，链表变成 1 -> 2 -> 3 -> 5，任务完成。

这里可以用一句话归纳：快指针多走的那一步，本质上是把两指针之间的窗口从“目标位置”平移到了“目标前驱”。慢指针最终停在哪，取决于窗口的右端对准的是 null 还是最后一个有效结点。记住这个规律，以后遇到“删除中间结点”“查找倒数第 k 个结点”这类变体，都可以迅速推出应该用哪种偏移量。

3.3 复杂度分析与面试加分表达

时间复杂度是 O(L)，L 为链表长度。fast 指针扫过整个链表一次，slow 指针最多也跟着走 L 步，总体仍是线性时间。空间复杂度是 O(1)，只用了两个指针变量和一个 dummy 结点。

面试里我建议你按这个顺序组织回答：先提两次遍历的 baseline 并分析它的开销；然后指出能否一次遍历；接着引出双指针思路，说明“快指针提前走 n 步，用窗口定位倒数位置”；再补充 dummy 结点对头结点删除的简化作用；最后用你熟悉的语言把代码写出来。这套表达下来，无论是逻辑严谨度还是代码风格，都比较接近面试官心里的标准答案。

还有一个常被追加的问题：如果 n 大于链表长度怎么办？LeetCode 原题通常会保证 n 有效，但如果题目没有明确约束，最好在实现里做防御。常见做法是让快指针先走 n 步，中途一旦遇到 null，说明 n 超界，直接返回原链表或抛出异常。具体返回什么看题目约定，口头说明你的处理策略也很重要。

4. 边界条件与典型案例验证

4.1 最容易出错的四类输入

第一类是链表只有一个结点。比如 [1]，n=1，删除后应返回空链表。用 dummy 版本看：快指针走 n+1=2 步，第一次从 dummy 走到结点 1，第二次从结点 1 走到 null。while 循环不执行，slow 仍然在 dummy。slow.next = slow.next.next 把唯一的结点删掉，返回 dummy.next 为 null。正确。

第二类是删除头结点。比如 [1,2,3,4,5]，n=5，目标删除头结点 1。快指针走 6 步，从链表里一路穿出去变成 null。循环不执行，slow 还在 dummy，删除 dummy.next 指向的 1，最终返回结点 2。整个过程不需要单独判断头结点，这就是 dummy 的功劳。如果你不用 dummy，这一步通常要写上if (n == length) return head.next;，多一个分支就多一分出错风险。

第三类是 n=1，删除最后一个结点。比如 [1,2,3]，n=1。快指针走 2 步，从 dummy 到结点 2。然后同步移动，fast 从 2 走到 null 需要 2 步，slow 从 dummy 走到结点 2。slow.next 此时是结点 3，把它改为 null，链表变成 [1,2]。这个场景考验的是“窗口开到最大时慢指针不能越界”。

第四类是 n 刚好等于链表长度，也就是删除头结点。它和第二类其实是同一个场景，但值得单独再跑一遍，因为很多人写循环时会在 n 等于长度时让快指针直接越界。用 dummy 版本时，快指针走 n+1 步正好到 null 后结束，不会出现访问 null.next 的情况。

4.2 用“纸上推演”的方式检查代码

有些同学写完链表代码后毫无把握，只能依赖编译器报错。我建议一个自带 debug 属性的训练方法：拿纸笔，把链表画成一排格子，左侧画一个 dummy 格，fast 和 slow 各用一个箭头表示。for 循环每执行一次，手动挪一次 fast 箭头；while 循环里同步挪两个箭头。来回走上两轮，你会清楚地看到 slow 到底停在第几个格子上。

这个方法看起来原始，但培养“指针移动后落在哪里”的直觉非常有效。我早年刷链表题时，就是靠画格子才彻底搞明白 prev 指针、dummy 结点、快慢指针之间的配合关系。画过几遍之后，你会发现链表题变来变去逃不出几个核心操作：找中点、找倒数第 k 个、反转片段、合并有序链。把这些操作的指针落点都画熟，遇到综合题也只是排列组合。

5. 常见错误与排查经验

5.1 空指针异常与漏判

跑这道题最常见的报错是空指针异常（NPE）。典型位置有两个。一是在 for 循环里快指针多走了超出链表长度的步数，fast 已经变成 null，下一轮循环还在访问 fast.next，直接抛异常。二是在删除步骤里 slow.next 本身就是 null，再去访问 slow.next.next 也会抛异常。

报错不一定代表思路错了，很可能是 n 和链表长度不匹配。如果题目保证 n 有效，那报错往往是循环次数多走了一步。检查思路很简单：手动推一遍快指针总共要走几次，数清楚最后一次赋值之后 fast 是 null 还是有效结点。对于 dummy 版本，快指针走 n+1 步，当 n 等于链表长度时，最后一次赋值恰好把 fast 推到 null，这时候 while 条件为 false，循环体不会进入，因此不会出现 null.next 的非法访问。理解了这个流程，就不会在循环条件里瞎猜。

5.2 快指针到底先走 n 还是 n+1

这可能是评论区里出现频率最高的问题。我把几种常见写法的关系整理出来，方便你对照：

从表里可以看出，前两行本质是等价的。第一行利用“快指针多走一步”的偏移；第二行利用“快指针最后停在有效结点而非 null”来缩短一次移动。第三行虽然也能做对，但没有 dummy 的辅助，需要额外处理 n 等于链表长度的情况。我的建议是：主记第一行，也就是 dummy 加 n+1 步的写法。它把 while 条件统一为fast != null，不需要思考 fast 停在倒数第一个结点时怎么办，逻辑最简单。

5.3 本地构造链表与调试技巧

刷题平台可以直接运行代码，但本地调试通常需要自己写链表构建和打印函数。我一般是写一个 buildList 方法，把数组转成链表，再写一个 printList 方法循环输出结点值。然后在本地把题目给的示例用例跑一遍，必要时用 IDE 的断点单步跟踪。

如果你想在代码里临时打印调试信息，也不是不行，但提交前记得删除干净。我见过有人把 System.out.println 留到了提交版本里，虽然判题通常不受影响，但代码在面试白板环节会显得不够严谨。调试时重点观察两个输出：快指针每次移动后停在谁的 next 上，以及删除操作前 slow.next 是否确实指向目标。这两处对了，整道题基本就不会错。

还有一个常用的排查技巧：把 n=1 和 n=链表长度这两组极端用例单独拿出来排序。前者对应链表尾删除，后者对应链表头删除，正好是快慢指针窗口的两个极端。这两组用例通过，大部分边界风险就已经被覆盖掉了。

6. 从这一题发散：链表系列的核心套路

6.1 倒数第K个结点与中间结点

第 19 题再往前走一步，就是另一道经典查点题：找到链表的倒数第 k 个结点。做法是快指针先走 k 步，然后快慢指针同步前进，快指针到达 null 时，慢指针正好指向目标结点。它和第 19 题的区别非常典型：查找节点只需要慢指针停在目标上，快指针走 k 步就行；删除节点需要慢指针停在目标前驱，所以快指针要多走一步，或者用 dummy 调整窗口。把握住这个差异，两题都能秒解。

再比如找链表中点，也是双指针：一个每次走一步，另一个每次走两步。快指针到尾部时，慢指针恰好在中点。这个“速度差”和“初始偏移差”是同一种工具的两个旋钮。前者决定两指针之间相对位移的变化速度，后者决定初始的起点距离。熟练之后，你会看到这些题本质上是同一个模型的不同参数组合。

6.2 双指针在链表题中的扩展

双指针能做的事情远不止查点和删点。判断链表是否有环就是用快慢指针，快指针每次跨两步，如果有环，两者最终会在环内相遇。找环的入口则是在相遇后，再让一个指针从链表头开始，一个从相遇点开始，每次各走一步，再次相遇的位置就是环入口。整个过程层层递进，每一步都依赖前一步推导出的位置关系。

此外，合并两个有序链表、求两个链表的交点、判断回文链表等题目，也会用到类似的“双指针移动不同步”的思想。链表题刷到中后期，你会发现它们是最容易“触类旁通”的一类题，因为底层工具就那么几种，区别只在于你把它用在哪个场景、让指针停在哪个位置。把第 19 题当成一个模板彻底吃透，对后续一系列问题都有帮助。

6.3 工程场景中的实际映射

有人觉得链表题只是面试工具，业务开发用不上。这个观点我不太认同。很多基础组件里的“窗口”“缓冲”“历史回退”其实都是链表或者更广义的“指针链”结构。比如限流算法里的滑动窗口，如果用链表维护时间点列表，一旦要删除超出时间窗口的“最老记录”，本质上就是在链表头部做删除；又比如某些缓存清理策略，需要淘汰最久未使用的记录，而这个队列如果采用单向链表组织，删除端点元素的逻辑和第 19 题处理头结点的方式几乎一致。

我在实际项目里清理一批过期消息时，就遇到过类似场景：队列中每个节点只知道后继消息的指针，需要定期移除“最老的一条”。当时脑子里很快就浮现出这道题的 dummy 结点思路，用一个哨兵节点统一了头部删除和普通删除，代码少写了不少分支。后来回想，刷题刷的不仅是算法，更是一种对边界条件和指针关系的敏感性，这套能力在工程里确实能派上用场。

我个人在反复做这道题的过程中，最大的体会是：写链表代码之前，一定要先想清楚“最终要停在哪里”。往大了说，所有的链表操作都是围绕“指针停靠位置”做文章；往小了说，这个习惯能让你少写很多追查空指针的时间。所以如果你刚开始刷链表，别觉得这种基础题简单，它值得你多写几遍，甚至试着自己画出不同变量组合下指针的落点。画清楚了，这一题带给你的纵深理解，会比你想象中多很多。