前言
「输出链表倒数第 k 个结点」是链表类题目里最经典的入门题，题面通常还附带一句「只允许遍历一次」。很多人的第一反应是先走一遍求出长度 n，再从头走 n−k 步，这样做虽然结果正确，但违反了一次遍历的限制；更常见的错误是边界没处理好——k 等于 0、k 大于链表长度、链表为空，这三种情况在面试里出现频率极高。
另一个容易混淆的点是「输出倒数 k 个结点」与「输出倒数第 k 个结点」。前者是一个子链表，后者是单个结点。本文按后者讲解，并在最后给出「删除倒数第 k 个结点」的扩展，因为删除操作才是真正考验指针操作的地方——它必须处理「删除头结点」这一特殊情况。
本文的代码以 C++17 为基准，用裸指针实现链表以贴近题目原本的形态，同时在示例里用 RAII 包装释放逻辑，避免演示程序自己泄漏内存。所有边界条件都会显式判断，不依赖「输入保证合法」这种假设。
一、朴素解法与它的代价
最直接的做法分两趟：第一趟统计结点个数 n，第二趟从头前进 n−k 步。时间复杂度 O(n)，空间 O(1)，思路清晰。但它要求链表可以被遍历两次，对于单向链表这没问题；如果数据来自只能顺序读取一次的流（例如网络包、迭代器只能前进的容器），第二趟就不成立了。
还有一个隐蔽问题：当 k 大于 n 时，n−k 是负数。如果长度用无符号类型存储，n - k会发生回绕，变成一个极大的正数，随后在循环里一路解引用空指针。这类错误在测试用例较弱时不容易暴露，一旦上线就是崩溃。
因此需要一种「一遍扫描、且天然处理越界」的方案。快慢指针正好满足：让快指针先走 k 步，如果中途遇到空指针，说明 k 超过长度，直接返回失败；否则快慢指针同步前进，快指针到尾时慢指针就在倒数第 k 个位置。
二、快慢指针的不变式
设链表长度为 n，快指针先走 k 步后，快慢指针之间相隔 k 个结点。此后两者同步前进，当快指针走过剩余的 n−k 个结点到达末尾时，慢指针恰好也走了 n−k 步，停在从前往后的第 n−k 个位置（从 0 开始计数），也就是倒数第 k 个。
这个论证成立的前提是「先走 k 步」这一步本身不越界。若在走的过程中fast变成空指针，说明 n < k，题目无解。注意判断时机：每走一步之前检查fast是否为空，而不是走完之后才检查，因为走完之后再解引用就已经晚了。
// 适用于 C++17
#include <iostream>
struct ListNode {
int value;
ListNode* next;
};
// 返回倒数第 k 个结点；k <= 0、链表为空、k 超长时返回 nullptr
ListNode* kthFromEnd(ListNode* head, int k) {
if (head == nullptr || k <= 0) {
return nullptr;
}
ListNode* fast = head;
ListNode* slow = head;
for (int i = 0; i < k; ++i) {
if (fast == nullptr) {
return nullptr; // k 大于链表长度
}
fast = fast->next;
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow;
}用几个小例子手工推演。链表1 -> 2 -> 3，k = 1：循环一次后fast指向 2，while让fast依次走到 3、空，slow依次走到 2、3，返回 3，正确。k = 3：循环三次后fast为空，while不执行，返回头结点 1，正确。k = 4：第三次循环后fast已为空，第四次进入循环体时检测到空并返回nullptr，正确。k = 0：函数开头直接返回nullptr，避免for循环一次都不执行导致返回头结点这种错误结果。
三、完整示例：构造、查询与释放
链表题在本地练习时，最麻烦的是手动new之后忘记delete。下面的示例用一个持有头指针的小结构体负责释放，构造阶段则用std::initializer_list简化。
// 适用于 C++17
#include <initializer_list>
#include <iostream>
#include <vector>
struct ListHolder {
ListNode* head = nullptr;
~ListHolder() {
while (head != nullptr) {
ListNode* next = head->next;
delete head; // new 与 delete 配对
head = next;
}
}
ListHolder(const ListHolder&) = delete;
ListHolder& operator=(const ListHolder&) = delete;
};
ListNode* buildList(const std::vector<int>& values) {
ListNode dummy{0, nullptr};
ListNode* tail = &dummy;
for (int v : values) {
tail->next = new ListNode{v, nullptr};
tail = tail->next;
}
return dummy.next;
}
int main() {
ListHolder holder;
holder.head = buildList({1, 2, 3, 4, 5});
for (int k = 1; k <= 6; ++k) {
ListNode* p = kthFromEnd(holder.head, k);
if (p != nullptr) {
std::cout << "k=" << k << " -> " << p->value << "\n";
} else {
std::cout << "k=" << k << " -> null\n";
}
}
return 0;
}buildList使用了哑结点（dummy node）技巧：栈上的dummy不参与堆分配，只作为临时的头前哨，最后返回dummy.next。这样插入逻辑统一，不需要为「第一个结点」写分支。ListHolder的析构函数逐个delete，与new ListNode{...}配对；拷贝构造和拷贝赋值被删除，避免两个 holder 持有同一条链表而重复释放。
注意ListNode dummy{0, nullptr};是聚合初始化，要求ListNode是聚合类型。如果以后给ListNode加了构造函数，这行就要改成显式构造。
四、扩展：删除倒数第 k 个结点
删除比查找多两步：一是要拿到待删结点的前驱，二是待删结点可能就是头结点。用哑结点可以把「删除头结点」和「删除中间结点」统一成同一种操作。
// 适用于 C++17
ListNode* removeKthFromEnd(ListNode* head, int k) {
if (k <= 0) {
return head;
}
ListNode dummy{0, head};
ListNode* fast = &dummy;
ListNode* slow = &dummy;
for (int i = 0; i < k; ++i) {
if (fast->next == nullptr) {
return head; // k 超过长度，原样返回
}
fast = fast->next;
}
while (fast->next != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode* victim = slow->next;
slow->next = victim->next;
delete victim;
return dummy.next;
}这里快慢指针都从&dummy出发，而不是从head出发。原因是删除需要前驱：当待删结点是头结点时，它的前驱是哑结点。若从head出发，slow最多只能停在头结点，拿不到「头结点之前」的位置，就不得不为删除头结点单独写一个分支。
推演一遍：链表1 -> 2，k = 2。fast从 dummy 走两步到结点 2；while (fast->next != nullptr)不执行；slow仍指向 dummy；victim是结点 1；dummy.next改为结点 2；删除结点 1；返回结点 2。正确。
若 k = 1，链表1 -> 2：fast走一步到结点 1；while中fast走到结点 2，slow走到结点 1；victim是结点 2；删除后返回结点 1。正确。
返回值必须是dummy.next而不是head，因为head可能已经被删除，此时它是指向已释放内存的悬垂指针。
常见坑点
坑点一：k 为 0 或负数时没有提前返回。
// ❌ 错误：for 循环一次不执行，直接返回头结点，语义完全不对
if (head == nullptr) return nullptr;
for (int i = 0; i < k; ++i) fast = fast->next;// ✅ 正确：把 k <= 0 当作非法输入
if (head == nullptr || k <= 0) return nullptr;坑点二：先移动再判空，导致空指针解引用。
// ❌ 错误：fast 已为空时还访问 fast->next
for (int i = 0; i < k; ++i) {
fast = fast->next;
if (fast == nullptr) return nullptr;
}// ✅ 正确：移动前判空
for (int i = 0; i < k; ++i) {
if (fast == nullptr) return nullptr;
fast = fast->next;
}坑点三：删除结点后返回了旧的head。
// ❌ 错误：删除的正是头结点时，head 已成悬垂指针
delete victim;
return head;// ✅ 正确：用哑结点并返回 dummy.next
return dummy.next;坑点四：长度用无符号类型做减法。
// ❌ 错误：k > n 时 n - k 回绕成极大值
std::size_t steps = n - k;
while (steps-- > 0) p = p->next;// ✅ 正确：先比较再相减，或改用快慢指针
if (k > n) return nullptr;坑点五：释放链表时先 delete 再读 next。
// ❌ 错误：delete 之后访问 p->next 是释放后使用
while (p) { delete p; p = p->next; }// ✅ 正确：先保存 next，再释放当前结点
while (p) { ListNode* n = p->next; delete p; p = n; }坑点六：把「倒数第 k 个」当成「倒数 k 个」实现。
// ❌ 错误：题目要单个结点，却返回了一整段子链表
ListNode* tail = kthFromEnd(head, k);
// 直接把 tail 当作结果输出全部剩余结点// ✅ 正确：明确题目要的是结点还是子链表，按语义返回
ListNode* node = kthFromEnd(head, k); // 单个结点坑点七：以为快慢指针必须从同一个位置出发。
// ❌ 错误：删除场景下 slow 从 head 出发，拿不到头结点的前驱
ListNode* slow = head;// ✅ 正确：需要前驱时让两者都从哑结点出发
ListNode* slow = &dummy;
ListNode* fast = &dummy;总结
| 场景 | 关键操作 | 边界 |
|---|
| 查找倒数第 k 个 | 快指针先走 k 步，再同步前进 | k ≤ 0、空表、k > n |
| 删除倒数第 k 个 | 两者从哑结点出发，slow 停在待删前驱 | 删除头结点、k > n |
| 内存释放 | 先存 next 再 delete | 不能边删边读 |
| 复杂度 | 时间 O(n)，空间 O(1) | 只遍历一趟 |
| 常见错误 | 判空时机、无符号减法、返回旧头指针 | 逐条显式处理 |
这道题的价值不在难度，而在于它强迫你把「指针间隔」和「边界检查」这两件事想清楚。把 k ≤ 0、k > n、删除头结点三种情况各写一行显式判断，代码就稳了；如果靠「题目保证输入合法」省掉这些判断，换一道题就会翻车。
函数详解)
