从哨兵到快慢指针：深入剖析「删除链表倒数第 N 个节点」的完整技术演进

引言

力扣第 19 题：给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

这道题看似简单，却像一颗洋葱——剥开一层，还有一层。它背后隐藏着链表操作中三大核心技巧的精妙融合：dummy 哨兵节点、链表反转思想、快慢指针策略。本文将带你从最基础的链表删除出发，层层递进，最终构建出高效、优雅、鲁棒的解决方案。

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

第一章：初识链表删除 —— 边界之痛与 dummy 节点的诞生

1.1 最朴素的删除实现（无 dummy）

假设我们要删除链表中值为val的第一个节点。最容易想到的写法如下：

function remove(head, val) { // 要删除的节点是头节点， 对头节点特殊处理 // 能不能省？头节点没有前驱节点，尾节点后没有后继节点 // 给它一个前驱节点 dummy 节点，假的 哨兵节点 // 遍历 if (head && head.val === val) { return head.next } let cur = head while(cur.next) { // 节点的遍历 if (cur.next.val === val) { cur.next = cur.next.next break; } cur = cur.next } return head }

这段代码逻辑清晰，但有一个致命弱点：必须对头节点做特殊判断。

为什么？因为在链表中，只有头节点没有前驱节点。当我们想删除某个节点时，通常需要修改其前一个节点的next指针。但对于头节点，没有“前一个”，只能直接返回head.next。

这就导致：

• 代码分支增多，可读性下降
• 容易遗漏边界情况（比如空链表、只有一个节点等）
• 无法统一处理所有删除场景

1.2 引入 dummy 节点：统一删除逻辑

为了解决这个问题，我们引入一个人为添加的假节点——dummy 节点（哨兵节点）。

function remove (head,val){ const dummy = new ListNode(0); dummy.next = head; let cur = dummy; while(cur.next) { if (cur.next.val === val) { cur.next = cur.next.next break; } cur = cur.next } return dummy.next }

dummy 节点的核心作用：

• 它不存储真实数据（值为 0 或任意占位符）
• 它的next指向原链表的头节点
• 它为原头节点提供了一个“虚拟前驱”

这样一来，所有节点（包括原头节点）都有了前驱！删除逻辑完全统一，无需任何特殊判断。

✅关键洞见：dummy 节点不是为了“解决问题”，而是为了“消除问题”——通过结构改造，让边界情况自然融入通用逻辑。

第二章：dummy 节点的高阶应用 —— 链表反转中的动态头指针

dummy 节点不仅用于删除，还能在构建新链表结构时大显身手。以链表反转为例：

// 使用dummy哨兵节点 + 头插法 function reverseList(head) { // 他的next将始终指向当前已反转部分的头节点 const dummy = new ListNode(0); let cur = head; while(cur) { // 先保存下一个节点 const next = cur.next; // 头插法 // 先将当前节点的next指向已反转部分的头节点 // 再将dummy的next指向当前节点，完成头插 cur.next = dummy.next; // 头插完成后，更新dummy的next指向当前节点 dummy.next = cur; // 头插完成后，更新当前节点为下一个节点 cur = next; } // 最后返回 dummy 的 next 节点，即新的头节点 return dummy.next; }

这里，dummy 节点扮演了动态头指针的角色：

• 初始时，dummy.next = null
• 每次将当前节点插入到dummy之后（即“头插”）
• dummy.next始终指向当前已反转部分的头节点

这个过程可以理解为：

原链表：1 → 2 → 3 → null 步骤1: 插入1 → dummy → 1 → null 步骤2: 插入2 → dummy → 2 → 1 → null 步骤3: 插入3 → dummy → 3 → 2 → 1 → null

最终返回dummy.next即为新头节点3。

✅关键洞见：dummy 节点不仅是“保护盾”，还可以是“指挥中心”——它的next指针可以动态维护某种结构状态（如反转链表的头）。

虽然反转与删除看似无关，但它们共享同一哲学：通过引入辅助结构，简化主逻辑。

第三章：定位难题 —— 如何在一次遍历中找到倒数第 N 个节点？

现在回到力扣第 19 题：删除倒数第 N 个节点。

3.1 朴素解法：两次遍历

最直接的想法：

1. 第一次遍历：计算链表长度L
2. 第二次遍历：走到第L - N个节点（即目标节点的前一个），执行删除

但题目隐含要求：最好只遍历一次（虽然未明说，但这是考察快慢指针的关键）。

3.2 快慢指针：一次遍历的魔法

快慢指针（Two Pointers）是解决“距离定位”类问题的经典技巧。

核心思想：

• 让两个指针fast和slow同时从起点出发
• fast先走N步
• 然后fast和slow一起每次走一步
• 当fast到达链表末尾（null）时，slow恰好位于倒数第 N 个节点的前一个

为什么？因为两者始终保持N步的距离！

图解示例：

链表：[1, 2, 3, 4, 5]，n = 2（删除 4）

初始： dummy → 1 → 2 → 3 → 4 → 5 → null ↑ fast, slow fast 先走 2 步： dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 然后一起走，直到 fast.next == null： dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ slow fast 此时 slow 指向 3，即倒数第 2 个节点（4）的前一个 执行 slow.next = slow.next.next → 删除 4

3.3 为什么必须用 dummy 节点？

考虑极端情况：删除头节点（即倒数第 L 个节点，L 为长度）

例如：[1, 2],n = 2→ 应删除1，返回[2]

如果没有 dummy：

• fast从head出发，走 2 步 →fast = null
• slow还在head
• 但我们需要的是“头节点的前一个”来执行删除，而它不存在！

有了 dummy：

• fast和slow从dummy出发
• fast走 2 步 → 指向2
• 然后fast.next为null，循环结束
• slow停在dummy，slow.next就是头节点1
• 执行slow.next = slow.next.next→ 完美删除头节点

关键洞见：快慢指针负责定位，dummy 节点负责安全删除——二者缺一不可。

第四章：终极融合 —— 力扣第 19 题的完整实现

现在，我们将前面所有知识融会贯通，写出最终解法：

// 删除链表的倒数第 N 个节点 const removeNthFromEnd = function(head, n) { // dummy 节点 const dummy = new ListNode(0); dummy.next = head; let fast = dummy; let slow = dummy; // 快指针先移动 N 步 for (let i = 0; i < n; i++) { fast = fast.next; } // 慢指针开始移动 while(fast.next) { // 末尾 fast = fast.next; slow = slow.next; } // 慢指针指向的就是倒数第 N 个结点的前一个 slow.next = slow.next.next; // dummy确保了 有值 return dummy.next; }

逐行解析：

1. 创建 dummy 节点

   const dummy = new ListNode(0); dummy.next = head;

   • 为整个链表添加虚拟头节点，统一后续操作

2. 双指针初始化

   let fast = dummy; let slow = dummy;

   • 两者都从 dummy 开始，确保能处理删除头节点的情况

3. 快指针先行 N 步

   for (let i = 0; i < n; i++) { fast = fast.next; }

   • 建立 fast 与 slow 之间的 N 步距离

4. 双指针同步移动

   while(fast.next) { fast = fast.next; slow = slow.next; }

   • 条件是fast.next而非fast，因为我们要让fast停在最后一个真实节点上
   • 此时slow恰好停在目标节点的前一个

5. 执行删除

   slow.next = slow.next.next;

   • 标准链表删除操作

6. 返回结果

   return dummy.next;

   • dummy 的 next 始终指向真正的头节点（即使原头被删）

第五章：边界情况全面验证

让我们验证几个关键测试用例：

情况1：删除中间节点

输入：[1,2,3,4,5],n=2
输出：[1,2,3,5]
✅ 正常工作

情况2：删除头节点

输入：[1,2],n=2
输出：[2]
✅ dummy 确保 slow 能定位到虚拟前驱

情况3：删除唯一节点

输入：[1],n=1
输出：[]（即null）

• fast 先走 1 步 → 指向1
• fast.next为null，不进入 while 循环
• slow 仍在 dummy
• slow.next = slow.next.next→dummy.next = null
• 返回null
  ✅ 正确

情况4：n 等于链表长度

同情况2，已覆盖
✅ 安全

第六章：与其他链表技巧的横向对比

6.1 与“判断链表是否有环”对比

判断环也用快慢指针：

function hasCycle(head) { let slow = head; let fast = head; while(fast && fast.next) { fast = fast.next.next; slow = slow.next; if (fast === slow) { return true; } } return false; }

区别：

• 目的不同：一个是检测相遇（环），一个是保持固定距离（定位）
• 起始点不同：环检测从head开始，删除从dummy开始
• 终止条件不同：环检测看是否相遇，删除看fast.next是否为空

但共通点是：利用速度差实现空间或位置关系的捕捉。

6.2 与“链表反转”对比

反转用 dummy 作为动态头，删除用 dummy 作为安全前驱。
相同点：都借助 dummy 简化逻辑
不同点：反转是构建，删除是破坏

第七章：总结 —— 三大技巧的协同哲学

这道题之所以经典，正是因为它不是单一技巧的展示，而是多个基础思想的有机融合。

编程的最高境界，不是记住多少算法，而是懂得如何组合基本构件，解决复杂问题。

附录：完整代码

// 删除链表的倒数第 N 个节点 const removeNthFromEnd = function(head, n) { // dummy 节点 const dummy = new ListNode(0); dummy.next = head; let fast = dummy; let slow = dummy; // 快指针先移动 N 步 for (let i = 0; i < n; i++) { fast = fast.next; } // 慢指针开始移动 while(fast.next) { // 末尾 fast = fast.next; slow = slow.next; } // 慢指针指向的就是倒数第 N 个结点的前一个 slow.next = slow.next.next; // dummy确保了 有值 return dummy.next; }

结语：
从一行删除代码的烦恼，到 dummy 节点的灵光一现；
从链表反转的头插法，到快慢指针的巧妙定位；
最终，我们在力扣第 19 题中见证了这些思想的完美交汇。

下次当你面对链表问题时，不妨自问：

我是否需要一个 dummy 来消除边界？
能否用快慢指针一次搞定？
多个指针如何分工协作？

答案，或许就藏在这篇长文中。