前言「输出链表倒数第 k 个结点」是链表类题目里最经典的入门题题面通常还附带一句「只允许遍历一次」。很多人的第一反应是先走一遍求出长度 n再从头走 n−k 步这样做虽然结果正确但违反了一次遍历的限制更常见的错误是边界没处理好——k 等于 0、k 大于链表长度、链表为空这三种情况在面试里出现频率极高。另一个容易混淆的点是「输出倒数 k 个结点」与「输出倒数第 k 个结点」。前者是一个子链表后者是单个结点。本文按后者讲解并在最后给出「删除倒数第 k 个结点」的扩展因为删除操作才是真正考验指针操作的地方——它必须处理「删除头结点」这一特殊情况。本文的代码以 C17 为基准用裸指针实现链表以贴近题目原本的形态同时在示例里用 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是否为空而不是走完之后才检查因为走完之后再解引用就已经晚了。// 适用于 C17#include iostreamstruct ListNode {int value;ListNode* next;};// 返回倒数第 k 个结点k 0、链表为空、k 超长时返回 nullptrListNode* 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 - 3k 1循环一次后fast指向 2while让fast依次走到 3、空slow依次走到 2、3返回 3正确。k 3循环三次后fast为空while不执行返回头结点 1正确。k 4第三次循环后fast已为空第四次进入循环体时检测到空并返回nullptr正确。k 0函数开头直接返回nullptr避免for循环一次都不执行导致返回头结点这种错误结果。三、完整示例构造、查询与释放链表题在本地练习时最麻烦的是手动new之后忘记delete。下面的示例用一个持有头指针的小结构体负责释放构造阶段则用std::initializer_list简化。// 适用于 C17#include initializer_list#include iostream#include vectorstruct 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::vectorint 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 个结点删除比查找多两步一是要拿到待删结点的前驱二是待删结点可能就是头结点。用哑结点可以把「删除头结点」和「删除中间结点」统一成同一种操作。// 适用于 C17ListNode* 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 - 2k 2。fast从 dummy 走两步到结点 2while (fast-next ! nullptr)不执行slow仍指向 dummyvictim是结点 1dummy.next改为结点 2删除结点 1返回结点 2。正确。若 k 1链表1 - 2fast走一步到结点 1while中fast走到结点 2slow走到结点 1victim是结点 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-nextfor (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.nextreturn 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、删除头结点三种情况各写一行显式判断代码就稳了如果靠「题目保证输入合法」省掉这些判断换一道题就会翻车。
