教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载导读本文基于 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 - 5k 1倒数第 1 个结点是值为 5 的尾结点。需要特别指出的是本题中k从 1 开始计数k 1表示尾结点k 链表长度表示头结点。这与数组下标从 0 开始的习惯不同是本题最容易出错的地方之一。二、方法一先遍历计数再正向定位2.1 思路单向链表的天然限制是只能从头往后走无法像数组一样通过下标随机访问。因此最直觉的做法分两步第一趟遍历从头结点开始统计链表总长度count换算正数位置倒数第 k 个结点等价于正数第count - k 1个结点从 1 计数第二趟遍历从头部出发走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)但两趟遍历意味着链表越长第二趟遍历带来的常数开销越明显更关键的是它丢失了一次遍历的面试加分点。在面试中面试官往往期望看到只遍历一次就能定位倒数第 k 个结点的方案这正是下面先后指针法的价值所在。三、方法二快慢指针先后指针一次遍历定位3.1 思路原文档中阿秀将其命名为快慢指针不应该说是先后指针这个命名其实非常精准与判断链表是否有环时一快一慢、速度不同的经典快慢指针不同本题中两个指针速度相同只是出发时间不同先手指针先行让pListHead先走k步过程中边走边判断 k 是否越界后手指针同步出发slowNode从头部出发此时它距离先手指针恰好k个结点一起前进直到先手指针走到链表末尾此时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为例步骤先手指针 pListHead 位置后手指针 slowNode 位置先手走第 1 步后结点 2结点 1进入第二个 while 循环结点 2结点 1同步前进 1 次结点 3结点 2同步前进 2 次结点 4结点 3同步前进 3 次结点 5结点 4同步前进 4 次nullptr循环结束结点 5✅当先手指针走到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 极大时可以在第一趟遍历的中途就提前返回。四、两种方法对比总结对比维度方法一先计数再定位方法二先后指针遍历次数2 趟严格 2n 步1 趟n 步时间复杂度O(n)O(n)空间复杂度O(1)O(1)k 越界处理先走完全程再判断count - k 0先手指针行走途中即时判断边界返回nullptrnullptr面试友好度直观、易写更优体现一次遍历思维两者都能 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 题的双指针思想吃透对刷通整个链表专题有直接的迁移价值。六、面试与笔试中的实战建议优先给出一次遍历解法先口述让一个指针先走 k 步再让第二个指针从头出发两者同步前进先手到底时后手即为答案再补代码面试官通常会对这种思路先行的作答方式更满意主动覆盖边界情况至少说明三种边界——空链表、k 1尾结点、k 链表长度返回空。这些边界正是本仓库二刷解法中用if (pListHead ! nullptr) ... else return nullptr;内联处理的部分注意计数起点k 从 1 计数而非从 0写代码和举例时都要保持一致避免 off-by-one 错误关注函数签名牛客网原题中 k 的类型为unsigned int这意味着k恒非负无需考虑k 0分支但若在力扣等其他平台实现需注意不同平台对 k 合法范围的定义可能略有差异以各平台题面为准。七、小结链表中倒数第 k 个结点是一道极具代表性的单链表基础题直观解法先统计长度、再走count - k步两趟遍历O(n) 时间、O(1) 空间容易想到也容易写对更优解法先后指针一次遍历O(n) 时间、O(1) 空间且能在行走途中即时拦截 k 越界是面试中的加分方案能力延伸双指针技巧可迁移到反转链表、求链表中间结点、判断链表是否有环快慢不同速等一系链表问题是校招、社招面试中必须掌握的算法基元。本仓库的 14-剑指offer.md 完整保留了阿秀的一刷、二刷解法记录与实测耗时适合作为刷题笔记反复对照汇总版 剑指offer全集.md 则适合整体通刷。坚持把每道题的多解与边界吃透面试时的手撕代码环节自然会从容许多。赞分享教程【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/gh_mirrors/in/InterviewGuide点击查看免费下载相关推荐剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点 本文基于 LeetCode Book 仓库中《剑指 Offer》第 22 题的解示例工程LogicStack-LeetCode 题解精读剑指 Offer 22 链表中倒数第 k 个节点的三种解法栈/队列、差值法、快慢指针LogicStack LeetCode 题解精读剑指 Offer 22 链表中倒数第 k 个节点的三种解法栈/队列、差值法、快慢指针 本文基于「宫水三叶的教程文档剑指 Offer 刷题笔记链表中倒数第 k 个结点——从双遍历到先后指针InterviewGuide 算法精讲剑指 Offer 刷题笔记链表中倒数第 k 个结点——从双遍历到先后指针InterviewGuide 算法精讲 本文围绕阿秀《带你快速刷完67道剑指off文档教程知识库上一篇解决DBeaver证书验证超时3步配置网络超时控制方案下一篇用 yomiyasu 推敲 AI 生成的 PR 说明文从同步改异步的 Token 刷新案例看「自然な日本語」改写全过程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
