企业官网建设流程全解析

• 教程

导读：本文基于 InterviewGuide 开源仓库中《剑指 Offer》刷题笔记 No14、链表中倒数第k个结点 展开，完整讲解该经典链表题的题目原型、示例输入输出，以及"先遍历计数再定位"与"双指针（先后指针）"两种 C++ 解法的思路、代码与边界处理，并从仓库其他链表题目（如反转链表、合并链表）出发，总结这类"一次遍历定位"问题在面试中的通用套路。读完本文，你将掌握如何用 O(n) 时间、O(1) 空间解决单向链表倒数第 k 个结点问题，并理解 k 越界、空链表等边界情况的稳健处理方式。

一、题目回顾

本专栏题目顺序与牛客网《剑指 Offer》专题保持一致，每道题都附带牛客网原题链接（详见 14-剑指offer.md）。

题目描述

输入一个链表，输出该链表中倒数第 k 个结点。

示例 1

输入

1,{1,2,3,4,5}

返回值

{5}

即链表为1 -> 2 -> 3 -> 4 -> 5，k = 1，倒数第 1 个结点是值为 5 的尾结点。

需要特别指出的是，本题中k从 1 开始计数：k = 1表示尾结点，k = 链表长度表示头结点。这与数组下标从 0 开始的习惯不同，是本题最容易出错的地方之一。

二、方法一：先遍历计数，再正向定位

2.1 思路

单向链表的天然限制是"只能从头往后走"，无法像数组一样通过下标随机访问。因此最直觉的做法分两步：

1. 第一趟遍历：从头结点开始，统计链表总长度count；
2. 换算正数位置：倒数第 k 个结点等价于正数第count - k + 1个结点（从 1 计数）；
3. 第二趟遍历：从头部出发走count - k步即可到达目标结点。

2.2 代码实现（仓库原解法）

这是阿秀在牛客网提交的第一版解法，完整保留在 14-剑指offer.md 中：

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { int count = 0; ListNode* node = pListHead; while (pListHead != nullptr) { count++; pListHead = pListHead->next; } count = count - k; if (count < 0) return nullptr; while (count--) node = node->next; return node; }

2.3 关键点解析

• 链表总长度count的计算：第一个while循环把pListHead一路走到nullptr，此时count即为结点总数；
• count - k的含义：倒数第 k 个结点与尾结点之间的距离为k - 1，因此从头结点到目标结点共需前进count - k步。例如链表长度 5、k = 1时，count - k = 4，从头走 4 步恰好到达尾结点；
• 越界判断：当k > count时，count - k < 0，说明第 k 个倒数结点根本不存在，直接返回nullptr。例如{1,2,3,4,5}且k = 6的场景；
• 时间复杂度 O(n)：两趟遍历，每趟 O(n)，总耗时约 2n；
• 空间复杂度 O(1)：只使用了两个指针变量。

2.4 方法一评价

原文档明确指出，该方法"时间复杂度较高，没有二刷的那种方法好"。虽然整体量级同为 O(n)，但两趟遍历意味着：

1. 链表越长，第二趟遍历带来的常数开销越明显；
2. 更关键的是，它丢失了"一次遍历"的面试加分点。在面试中，面试官往往期望看到只遍历一次就能定位倒数第 k 个结点的方案，这正是下面"先后指针"法的价值所在。

三、方法二：快慢指针（先后指针），一次遍历定位

3.1 思路

原文档中阿秀将其命名为"快慢指针，不应该说是先后指针"，这个命名其实非常精准：与"判断链表是否有环"时一快一慢、速度不同的经典快慢指针不同，本题中两个指针速度相同，只是出发时间不同：

1. 先手指针先行：让pListHead先走k步（过程中边走边判断 k 是否越界）；
2. 后手指针同步出发：slowNode从头部出发，此时它距离先手指针恰好k个结点；
3. 一起前进直到先手指针走到链表末尾：此时slowNode恰好停在倒数第 k 个结点上。

3.2 代码实现（仓库二刷解法）

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode* slowNode = pListHead; while (k != 0) { // 先手指针先走 k 步 k--; if (pListHead != nullptr) pListHead = pListHead->next; // 走一步就判断一次是否越界 else return nullptr; // k 大于链表长度，直接返回 } while (pListHead != nullptr) { // 先手指针未到末尾时，两指针同步前进 slowNode = slowNode->next; pListHead = pListHead->next; } return slowNode; }

原文档中此解法在牛客网实测：3 ms，占用内存 376K（不同提交环境、不同用例规模下数值会有浮动，仅供参考）。

3.3 逐步推演

以{1,2,3,4,5}、k = 1为例：

当先手指针走到nullptr时，后手指针正好落在倒数第 1 个结点（尾结点）上。

再以{1,2,3,4,5}、k = 5为例：先手指针走 5 步后恰好也到达nullptr，此时第二个 while 循环一次都不执行，slowNode停留在头结点上，正确返回倒数第 5 个结点（头结点）。

3.4 边界情况：k 大于链表长度

本题最容易踩的坑是k > 链表长度，例如{1,2,3,4,5}且k = 6。此时倒数第 6 个结点不存在，按题目语义应返回空。

在双指针解法中，这一判断被内嵌进先手指针的行走过程：先手指针每走一步前都检查pListHead是否为nullptr，若在走完 k 步之前就已经触空，说明链表长度不足 k，立即返回nullptr，无需第二趟遍历。

while (k != 0) { k--; if (pListHead != nullptr) pListHead = pListHead->next; else return nullptr; // k 太大，链表提前走完 }

这一设计比"先完整遍历统计长度再判断"更加高效：在极端情况下（k 极大时）可以在第一趟遍历的中途就提前返回。

四、两种方法对比总结

两者都能 AC，但方法二在面试中明显更有亮点：它把"链表的单向不可回退"这一限制，转化为"两个指针拉开固定距离再平移"的经典技巧，体现了对单向链表结构本质的理解。

五、进阶：同一技巧在仓库其他链表题中的应用

"双指针拉开距离"并非孤立技巧。在 InterviewGuide 的剑指 Offer 刷题笔记中，链表题还大量出现与之同源的思路：

5.1 反转链表：双指针迭代

15-剑指offer.md 中的反转链表问题，二刷解法使用pre / cur / after三个指针不断更替完成原地反转：

ListNode* ReverseList(ListNode* pHead) { if (pHead == nullptr || pHead->next == nullptr) return pHead; ListNode *pre = nullptr, *cur = pHead, *after = pHead->next; while (cur != nullptr) { cur->next = pre; pre = cur; cur = after; if (after != nullptr) after = after->next; } return pre; }

这里同样体现了"用有限个指针变量维护链表的相邻关系"的核心思想——与本题的先后指针异曲同工，都是对单向链表"只能单向移动"这一特性的精巧利用。

5.2 合并两个有序链表：递归与迭代

16-剑指offer.md 的合并有序链表题，先处理pHead1 == nullptr/pHead2 == nullptr的边界，再比较头结点值递归或迭代合并。其边界判断习惯（先把空指针情况处理干净，再进入主体逻辑）同样适用于本题：pListHead == nullptr时应直接返回nullptr。

5.3 复杂链表的复制：指针重组

25-剑指offer.md 的复杂链表复制，本质是把"复制节点插入原链表 → 处理 random 指针 → 拆分链表"三段式操作串联起来，全程只依赖指针操作完成深拷贝。

从源码结构看，本仓库剑指 Offer 笔记中的链表题（第 14、15、16、25 题等，汇总版见 剑指offer全集.md）呈现出高度一致的解题范式：空指针边界优先处理、有限指针变量维护关系、一次遍历解决问题。把第 14 题的双指针思想吃透，对刷通整个链表专题有直接的迁移价值。

六、面试与笔试中的实战建议

1. 优先给出一次遍历解法：先口述"让一个指针先走 k 步，再让第二个指针从头出发，两者同步前进，先手到底时后手即为答案"，再补代码，面试官通常会对这种"思路先行"的作答方式更满意；
2. 主动覆盖边界情况：至少说明三种边界——空链表、k = 1（尾结点）、k > 链表长度（返回空）。这些边界正是本仓库二刷解法中用if (pListHead != nullptr) ... else return nullptr;内联处理的部分；
3. 注意计数起点：k 从 1 计数而非从 0，写代码和举例时都要保持一致，避免 off-by-one 错误；
4. 关注函数签名：牛客网原题中 k 的类型为unsigned int，这意味着k恒非负，无需考虑k < 0分支；但若在力扣等其他平台实现，需注意不同平台对 k 合法范围的定义可能略有差异（以各平台题面为准）。

七、小结

"链表中倒数第 k 个结点"是一道极具代表性的单链表基础题：

• 直观解法：先统计长度、再走count - k步，两趟遍历，O(n) 时间、O(1) 空间，容易想到也容易写对；
• 更优解法：先后指针一次遍历，O(n) 时间、O(1) 空间，且能在行走途中即时拦截 k 越界，是面试中的加分方案；
• 能力延伸：双指针技巧可迁移到反转链表、求链表中间结点、判断链表是否有环（快慢不同速）等一系链表问题，是校招、社招面试中必须掌握的算法基元。

本仓库的 14-剑指offer.md 完整保留了阿秀的一刷、二刷解法记录与实测耗时，适合作为刷题笔记反复对照；汇总版 剑指offer全集.md 则适合整体通刷。坚持把每道题的多解与边界吃透，面试时的"手撕代码"环节自然会从容许多。

• 教程