企业官网建设流程全解析

在链表相关的算法题中，边界条件的处理往往是让人最容易翻车的地方。特别是当我们需要删除或插入头节点时，由于头节点没有“前驱节点”，我们往往不得不编写额外的 if-else 逻辑来特殊处理。

今天，我们将以经典的LeetCode 19. 删除链表的倒数第 N 个结点为例，分享哨兵节点（Dummy Node）。

一、 为什么需要哨兵节点？

在单链表中，如果我们想要删除一个节点 Target，标准的操作是找到它的前驱节点 Prev，然后执行：

Prev->next = Target->next;

这就带来一个痛点：如果我们要删除的Target恰好是头节点（Head）呢？

头节点没有前驱节点，我们无法使用上述统一逻辑，只能被迫写成这样：

if (head == target) { head = head->next; // 特殊处理头节点 } else { // 寻找前驱节点，执行 prev->next = prev->next->next; }

这种特殊判断不仅代码丑陋，而且在复杂的逻辑中极容易遗漏，导致空指针异常。

哨兵节点（Dummy Node）的魔法：

我们在真实链表的头节点前面，人为地加上一个虚拟节点 dummy。

链表变成了：dummy -> head -> node2 -> node3 ...

此时，原本的 head 不再特殊，它有了前驱节点 dummy。

删除原本的 head 只需要统一执行：dummy->next = dummy->next->next;。

二、 LeetCode 19 解题思路（题目链接）

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

1. 核心难点

我们不知道链表有多长，所以无法直接找到倒数第 n 个节点。常规思路是先遍历一次计算长度 L，然后再遍历一次找到正数第 L - n + 1 个节点删除。但这需要遍历两次。

2.解法尝试：计算链表长度 + 哨兵节点

“先计算总长度，再正向遍历寻找前驱节点”是最符合直觉的解法。结合我们前面提到的哨兵节点，可以写出非常清晰的代码。

核心思路：

1. 引入哨兵节点：创建 dummy 指向 head，统一删除头节点的逻辑。
2. 第一遍遍历（算长度）：用一个指针遍历链表，计算出链表的总长度 length。
3. 计算正向位置：要删除倒数第 n 个节点，其实就是删除正数第 length - n + 1 个节点。那么，它的前驱节点就是正数第 length - n 个节点。
4. 第二遍遍历（找前驱）：让指针从 dummy 出发，走 length - n 步，停在待删除节点的前驱上。
5. 执行删除：cur->next = cur->next->next;，最后返回 dummy->next。

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 1. 创建哨兵节点，统一删除头节点的逻辑 ListNode* dummy = new ListNode(0, head); if (head == nullptr) return nullptr; // 边界情况处理 // 2. 第一遍遍历：计算链表总长度 int length = 0; ListNode* temp = head; while (temp != nullptr) { length++; temp = temp->next; } // 3. 第二遍遍历：寻找待删除节点的前驱节点 // 倒数第 n 个节点的前驱，即正数第 (length - n) 个节点 ListNode* cur = dummy; for (int i = 0; i < length - n; i++) { cur = cur->next; } // 4. 执行删除操作 ListNode* nodeToDelete = cur->next; cur->next = cur->next->next; delete nodeToDelete; // 释放内存 // 5. 返回新的头节点 ListNode* result = dummy->next; delete dummy; return result; } };

2. 最优解：快慢指针 + 哨兵节点

为了只遍历一次，我们引入快慢指针。

1. 定义哨兵节点：dummy->next = head。定义快指针 fast 和慢指针 slow，初始都指向 dummy。
2. 快指针先走n + 1步：为什么是 n + 1 步？因为我们要让 fast 和 slow 之间相隔 n + 1 个节点的距离。
3. 快慢指针同步前进：当 fast 走到链表末尾的 nullptr 时，由于它们相距 n + 1，此时 slow 刚好停留在倒数第n + 1个节点（也就是待删除节点的前驱节点）上。
4. 执行删除：slow->next = slow->next->next;
5. 返回结果：return dummy->next;

3. 代码实现 (C++)

class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { // 1. 创建哨兵节点，指向头节点 ListNode* dummy = new ListNode(0, head); ListNode* fast = dummy; ListNode* slow = dummy; // 2. 快指针先走 n + 1 步 for (int i = 0; i <= n; i++) { fast = fast->next; } // 3. 快慢指针同步移动，直到快指针为空 while (fast != nullptr) { fast = fast->next; slow = slow->next; } // 4. 此时 slow 指向待删除节点的前驱节点，执行删除 ListNode* temp = slow->next; // 记录待删除节点 slow->next = slow->next->next; delete temp; // 释放内存 (C++ 良好习惯) // 5. 返回哨兵节点的下一个节点，即新的头节点 ListNode* result = dummy->next; delete dummy; // 释放哨兵节点 return result; } };

三、关于哨兵节点的三个拷问

拷问 1：为什么最后一定要 return dummy->next; 而不能 return head;？

解答：因为我们无法确定原来的 head 是否被删除了。
假设链表是 [1]，n = 1。此时我们要删除头节点 1。
执行删除后，dummy->next 变成了 nullptr。而原来的 head 指针依然指向那个已经被释放的节点 1。
如果返回 head，就会返回一个错误的野指针。而 dummy->next 永远指向链表现在真正的头节点。

拷问 2：为什么快指针要先走 n + 1 步？

解答：为了让慢指针停在前驱节点上。
假设 n = 2。快指针走 3 步（n+1）。
初始状态：dummy(0) -> 1 -> 2 -> 3 -> 4 -> 5。
fast 走到 3。此时 slow 还在 dummy。
两者距离是 3（dummy 到 3 的节点数）。
接下来 fast 和 slow 一起走。当 fast 走到 nullptr（5 的下一个）时，slow 刚好走到 3。
3 正是倒数第 2 个节点（4）的前驱节点！如果快指针只走 n 步，慢指针最终会停在 4 上，我们就无法删除 4 了（因为找不到前驱节点）。

拷问 3：操作链表时，为什么 dummy 本身不能动？

解答：dummy 是我们的“锚点”。如果你写了 dummy = dummy->next;，那么 dummy 就往前跑了，最后你返回 dummy->next 时，返回的就不再是完整的链表头了。
正确的做法是：让dummy永远钉在原地，创建一个临时指针（如cur,fast,slow）从dummy出发去遍历。