企业官网建设流程全解析

前言

"删除链表的倒数第 N 个结点"是链表练习里非常经典的一道题。朴素做法是先遍历一遍求长度L，再从头走L - N步删掉目标；进阶要求是只遍历一趟。一趟解法的核心是快慢指针：让快指针先走出一段固定距离，然后两个指针同步前进，快指针到末尾时慢指针恰好停在待删结点的前驱上。

这道题真正的难点不在指针技巧，而在边界：删除的正好是头结点怎么办？N等于链表长度怎么办？N非法（大于长度或小于 1）怎么办？很多人写出的代码在"删头"这一种情况上出错，因为头结点没有前驱，无法用统一的方式改链。

本文先写两趟解法作为对照，再推演一趟解法的步数关系，重点解释哑结点（dummy node）为什么能让删头与删中间用同一段代码，最后给出可独立运行的完整示例。代码以 C++17 为基准。

一、朴素解法：先求长度再定位

链表没有下标，要删倒数第 N 个，最直接的办法是把它换算成正数第L - N + 1个，于是需要先知道L。

// 适用于 C++17
struct ListNode {
int val;
ListNode* next;
explicit ListNode(int v) : val(v), next(nullptr) {}
};

ListNode* removeNthFromEnd_twoPass(ListNode* head, int n) {
int len = 0;
for (ListNode* p = head; p != nullptr; p = p->next) ++len;
if (n <= 0 || n > len) return head; // 非法输入，原样返回

ListNode dummy(0);
dummy.next = head;
ListNode* prev = &dummy;
for (int i = 0; i < len - n; ++i) {
prev = prev->next;
}
ListNode* victim = prev->next;
prev->next = victim->next;
delete victim;
return dummy.next;
}

即使是最朴素的两趟解法，也用了哑结点：prev从&dummy出发，走len - n步后停在待删结点的前一个。当len == n（删头）时，循环一步不走，prev仍是&dummy，dummy.next被改成原头的后继，返回dummy.next就是新头。如果没有哑结点，删头就要单独写一个分支。

时间 O(L)，空间 O(1)。

二、一趟解法：快慢指针的步数关系

要让慢指针停在待删结点的前驱，需要满足：当快指针走到nullptr时，慢指针距离末尾恰好是N + 1个结点（即慢指针的后继是倒数第 N 个）。

设快指针先走k步，此后两者同步前进。快指针总共走了L + 1步（从哑结点出发，走到空），慢指针走了L + 1 - k步。慢指针需要停在从前往后第L - N个位置（0 基，哑结点为 0），即走L - N步。于是：

L + 1 - k = L - N => k = N + 1

所以快指针先走N + 1步，不是N步。这是最容易写错的地方：走N步时，快指针到空时慢指针停在待删结点本身，拿不到前驱，无法改链。

// 适用于 C++17
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (n <= 0) return head;

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

ListNode* fast = &dummy;
ListNode* slow = &dummy;

for (int i = 0; i < n + 1; ++i) {
if (fast == nullptr) return head; // n 超过链表长度
fast = fast->next;
}

while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}

ListNode* victim = slow->next;
slow->next = victim->next;
delete victim;
return dummy.next;
}

按标准语义推演两个边界：

• 
  
• 链表1 -> 2 -> 3 -> 4 -> 5，n = 2。快指针从哑结点走 3 步到结点 3，慢指针在哑结点；同步走 3 次后快指针为空，慢指针到结点 3，slow->next是结点 4，正是倒数第 2 个。
• 
  
• 同一链表，n = 5。快指针走 6 步后为空，慢指针仍在哑结点，slow->next是原头结点，删除后返回dummy.next即结点 2。
• 
  

n + 1次前进里带了空指针检查：如果n大于链表长度，快指针会在中途变成空，此时直接返回原链表，不修改任何结点。这是防御性写法；如果题目保证n合法，可以省略，但保留它不会影响正常路径。

三、哑结点到底解决了什么

哑结点是一个栈上的临时结点，next指向真正的头。它带来的好处是：头结点也有了"前驱"。删除操作统一成"改前驱的next"，不需要判断victim == head。

对比一下没有哑结点的写法：

// 适用于 C++17：没有哑结点，必须特判删头
ListNode* remove_without_dummy(ListNode* head, int n) {
ListNode* fast = head;
for (int i = 0; i < n; ++i) {
if (!fast) return head;
fast = fast->next;
}
if (!fast) { // 删的正是头结点
ListNode* new_head = head->next;
delete head;
return new_head;
}
ListNode* slow = head;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* victim = slow->next;
slow->next = victim->next;
delete victim;
return head;
}

这段代码也能工作，但多了一个分支，而且两个分支的步数关系不一样（快指针先走n步，循环条件用fast->next），读起来更容易出错。哑结点把"删头"和"删中间"合并成一条路径，代价只是一个栈上的结点和一个指针，可以忽略。

需要强调的是：哑结点是栈对象，不能delete它，也不能把它返回给调用方。函数返回的是dummy.next，哑结点在函数结束时随作用域销毁，它的next已经被复制出去了。

四、完整示例

把结点构造、链表打印、释放和主流程拼在一起。下面的destroy负责释放整条链，避免示例本身泄漏。

// 适用于 C++17
#include <initializer_list>
#include <iostream>

ListNode* build(std::initializer_list<int> vals) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int v : vals) {
tail->next = new ListNode(v);
tail = tail->next;
}
return dummy.next;
}

void destroy(ListNode* head) {
while (head != nullptr) {
ListNode* next = head->next;
delete head;
head = next;
}
}

void print(const ListNode* head) {
for (const ListNode* p = head; p != nullptr; p = p->next) {
std::cout << p->val;
if (p->next) std::cout << " -> ";
}
std::cout << '\n';
}

int main() {
ListNode* head = build({1, 2, 3, 4, 5});
head = removeNthFromEnd(head, 2); // 删除结点 4
print(head);
destroy(head);

head = build({1});
head = removeNthFromEnd(head, 1); // 删除唯一的结点，返回空链表
print(head); // 不输出任何值
destroy(head);
}

第二步head = removeNthFromEnd(head, 1)之后head为nullptr，print与destroy都能安全处理空链表，这也说明"返回新头"这个约定必须被调用方接住——如果写成removeNthFromEnd(head, 1);而忽略返回值，删头之后调用方手里的还是悬垂指针。

复杂度：时间 O(L)，只遍历一趟；空间 O(1)，只用了两个指针和一个哑结点。

常见坑点

1. 快指针先走 N 步而不是 N + 1 步

// ❌ 慢指针停在待删结点上，拿不到前驱
for (int i = 0; i < n; ++i) fast = fast->next;
// ✅ 多走一步，让慢指针停在前驱
for (int i = 0; i < n + 1; ++i) fast = fast->next;

2. 删头时没有更新返回值

// ❌ 返回的仍是已经 delete 的旧头
delete victim;
return head;
// ✅ 统一返回 dummy.next
delete victim;
return dummy.next;

3. 删除后继续访问被删结点

// ❌ victim 已释放，next 是悬垂读取
delete victim;
slow->next = victim->next;
// ✅ 先改链，再释放
slow->next = victim->next;
delete victim;

4. 对栈上的哑结点执行 delete

// ❌ 未定义行为：dummy 不是 new 出来的
ListNode dummy(0);
delete &dummy;
// ✅ 哑结点随作用域自动销毁

5. 不检查 N 越界

// ❌ n 大于长度时快指针变空，后续解引用崩溃
for (int i = 0; i < n; ++i) fast = fast->next;
// ✅ 每一步判空
if (fast == nullptr) return head;

6. 结点的所有权不清晰就 delete

// ❌ 若链表由别处管理，这里 delete 会造成重复释放
delete victim;
// ✅ 明确本函数拥有结点时才释放，否则只改链
slow->next = victim->next;

7.n = 0或负数未处理

// ❌ 循环条件异常，可能走到非法位置
if (n < 1) { /* 未处理 */ }
// ✅ 入口直接拒绝
if (n <= 0) return head;

8. 用while (fast->next)却在快指针已为空时进入

// ❌ fast 为空时解引用
while (fast->next) { ... }
// ✅ 先判空，或改用 while (fast)
while (fast != nullptr) { ... }

总结

这道题的价值在于训练"用相对距离代替绝对下标"的思维：链表拿不到长度，但可以让两个指针保持固定间距。把间距设为N + 1而不是N，再配一个哑结点抹平删头的特判，代码就只剩一个循环和一次改链。记住这两个数字的来源（一个是"要停在前驱"，一个是"头也需要前驱"），比背代码更可靠。