示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 开源题解仓库中 《面试题 02.02. 返回倒数第 k 个节点》 的官方题解为核心完整讲解单向链表倒数第 k 个节点问题的快慢指针解法并覆盖 Python、Java、C、Go、TypeScript、Rust、JavaScript、Swift 八种语言的实现细节。读完本文你将掌握一趟扫描 常数空间定位链表倒数第 k 个节点的通用套路并能在仓库内同类题目剑指 Offer 22、剑指 Offer II 021中举一反三。题目背景与问题描述本题来自《程序员面试金典第 6 版》第 2 章链表部分题目编号02.02在仓库中的完整题解位于 lcci/02.02.Kth Node From End of List/README.md。题目要求实现一种算法找出单向链表中倒数第 k 个节点返回该节点的值。示例输入1 - 2 - 3 - 4 - 5 和 k 2 输出4两个重要说明注意本题相对原书题目稍作改动。原书CTCI 2.2通常要求返回倒数第 k 个节点这个节点本身而本题改为返回该节点的值函数签名也相应变为kthToLast(head, k) - int给定的 k 保证是有效的即满足1 ≤ k ≤ nn 为链表长度因此在官方题解中不需要对 k 做合法性校验也无需在链长为 0 时做空指针兜底。解法核心快慢指针方法一思路推导直观思路是把倒数转化为正数倒数第 k 个节点等价于正数第n - k 1个节点。由此得到最朴素的两趟遍历方案第一趟扫描链表统计长度 n第二趟从头走n - k步即可定位目标节点。该方案正确且 n 通常不大但题目希望一趟遍历完成。观察到一个关键性质若快指针比慢指针提前 k 步那么当快指针抵达链表末尾null时慢指针恰好停在倒数第 k 个节点上。这正是快慢指针双指针解法的核心思想——把未知的链表长度这个信息转化为两指针之间的固定步距从而无需预先知道 n。算法步骤定义两个指针slow和fast初始时都指向链表头节点headfast指针先向前移动 k 步然后slow与fast指针同时向前移动每次各走一步直到fast指针指向链表末尾为空时停止此时slow指针指向的节点就是倒数第 k 个节点返回slow.val。整个过程只扫描链表一次时间复杂度 O(n)其中 n 是链表的长度全程只使用两个指针变量空间复杂度 O(1)。示例逐步推演以1 - 2 - 3 - 4 - 5、k 2为例步骤fast 指向slow 指向说明初始化节点 1节点 1两指针同起于头节点fast 走第 1 步节点 2节点 1fast 先行fast 走第 2 步节点 3节点 1fast 共领先 k2 步同步前进 1节点 4节点 2两指针间距保持 2同步前进 2节点 5节点 3两指针间距保持 2同步前进 3null末尾节点 4fast 为空循环结束循环结束时slow指向节点 4即倒数第 2 个节点与题目输出一致。八种语言实现详解以下实现均继承自官方题解并与仓库中对应的 Solution 文件保持一致。读者可在 lcci/02.02.Kth Node From End of List 目录下查看各语言的独立源文件。Python3对应源文件Solution.pyclass Solution: def kthToLast(self, head: ListNode, k: int) - int: slow fast head for _ in range(k): fast fast.next while fast: slow slow.next fast fast.next return slow.valfor _ in range(k)让fast先行 k 步随后while fast以fast是否为None作为终止条件循环结束后直接返回slow.val简洁直观。Java对应源文件Solution.javaclass Solution { public int kthToLast(ListNode head, int k) { ListNode slow head, fast head; while (k-- 0) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; } }利用k-- 0的后置自减写法把走 k 步压缩为一行循环第二个while以fast ! null为循环条件语义与 Python 版本完全对应。C对应源文件Solution.cppclass Solution { public: int kthToLast(ListNode* head, int k) { ListNode* fast head; ListNode* slow head; while (k--) { fast fast-next; } while (fast) { slow slow-next; fast fast-next; } return slow-val; } };C 版本使用原生指针while (k--)依赖k递减到 0 时退出第二个循环以指针本身非空即真作为条件与 Go 的写法习惯相近。Go对应源文件Solution.gofunc kthToLast(head *ListNode, k int) int { slow, fast : head, head for ; k 0; k-- { fast fast.Next } for fast ! nil { slow slow.Next fast fast.Next } return slow.Val }Go 版本用for ; k 0; k--显式控制步数第二个循环以fast ! nil终止语义清晰注意 Go 中字段名为Val、Next首字母大写。TypeScript对应源文件Solution.tsfunction kthToLast(head: ListNode | null, k: number): number { let [slow, fast] [head, head]; while (k--) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; }TypeScript 版本用解构赋值let [slow, fast] [head, head]一次性初始化两个指针并在类型层面显式标注head: ListNode | null在k保证有效的前提下fast.next与slow.val的访问是安全的。Rust对应源文件Solution.rsimpl Solution { pub fn kth_to_last(head: OptionBoxListNode, k: i32) - i32 { let mut fast head; for _ in 0..k { fast fast.as_ref().unwrap().next; } let mut slow head; while let (Some(f), Some(s)) (fast, slow) { fast f.next; slow s.next; } slow.as_ref().unwrap().val } }Rust 版本最能体现语言特性链表以OptionBoxListNode表示fast、slow均为对head的不可变引用。fast.as_ref().unwrap().next在先行阶段逐层取得下一节点的引用同步阶段通过while let (Some(f), Some(s))同时解构两个引用并前进最终slow.as_ref().unwrap().val取出目标值。整个过程零拷贝、零所有权转移充分说明快慢指针算法在所有权严格的语言中同样可以优雅落地。JavaScript对应源文件Solution.jsvar kthToLast function (head, k) { let [slow, fast] [head, head]; while (k--) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; };JavaScript 与 TypeScript 的实现几乎一致仅少类型标注while (k--)的写法在k递减为 0 时自动退出循环。Swift对应源文件Solution.swiftclass Solution { func kthToLast(_ head: ListNode?, _ k: Int) - Int { var slow head var fast head var k k while k 0 { fast fast?.next k - 1 } while fast ! nil { slow slow?.next fast fast?.next } return slow?.val ?? 0 } }Swift 版本使用可选链fast?.next遍历fast为ListNode?并对入参k做了局部拷贝var k k以便递减返回时用slow?.val ?? 0对可选值兜底——在 k 保证有效的前提下实际取值必然是目标节点的值。仓库源码佐证与题解组织方式doocs/leetcode 仓库对每道题的组织遵循统一约定每个题目目录下包含README.md中文题解、README_EN.md英文题解以及按语言命名的独立 Solution 文件。以本题为例lcci/02.02.Kth Node From End of List 目录包含README.md —— 中文题解本文主体内容的来源README_EN.md —— 英文题解解法与中文版一一对应Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.swift —— 共 8 个语言版本。需要特别说明的是lcci目录整体对应《程序员面试金典第 6 版》题号02.02中的02代表第 2 章链表。仓库中同一算法思想还以不同变体出现在多个目录中这正是我们下一节要展开的内容。算法正确性与复杂度论证为什么慢指针最终一定落在倒数第 k 个节点设链表长度为 n。当fast先走完 k 步后slow仍在头节点两指针间距恒为 k。此后两指针每次同步前进一步间距保持不变。当fast走到末尾null时它从起点共走了 n 步链表共有 n 个节点从第 1 个节点走到 null 需要 n 步而slow比fast少走 k 步共走了n - k步恰好落在正数第n - k 1个节点上——这正是倒数第 k 个节点。复杂度时间复杂度 O(n)fast先行 k 步、随后两指针同步前进合计恰好遍历一遍链表空间复杂度 O(1)仅使用两个指针变量不依赖链表长度。相比两趟遍历方案先数长度、再走n - k步快慢指针在渐进复杂度同为 O(n) 的前提下把扫描压缩为一趟常数更小也是面试中更受青睐的写法。边界情况讨论由于题目保证k有效1 ≤ k ≤ n官方实现无需额外保护但理解边界仍有助于加深对算法不动点的把握k 1尾节点fast先行 1 步后两指针同步前进当fast到达 null 时slow恰好位于最后一个节点返回尾节点值k n头节点fast先行 n 步后直接为 null第二个循环一次都不执行slow仍指向头节点返回头节点值若题目不保证 k 有效如k n或链表为空上述实现会在先行阶段对fast解引用空指针而崩溃此时需要先校验长度或增加空指针判断——这是实战中需要根据题目约束灵活调整的地方。仓库内同类题目的变式延伸快慢指针解决倒数第 k类问题的套路在 doocs/leetcode 仓库中还有两个典型变式可作为练习与对比变式一剑指 Offer 22 —— 返回节点而非值《面试题 22. 链表中倒数第 k 个节点》 与本题算法骨架完全一致唯一区别是返回类型该题要求返回倒数第 k 个节点本身ListNode*而本题返回int值。对比两个版本的函数签名与返回语句可以清晰看到同一算法在不同接口约束下的适配方式。变式二剑指 Offer II 021 —— 删除倒数第 n 个结点《剑指 Offer II 021. 删除链表的倒数第 n 个结点》 把定位升级为定位并删除。删除操作需要访问目标节点的前驱因此该题引入哨兵节点dummy ListNode(nexthead)让slow、fast都从dummy出发fast先行n 1步同步前进直到fast为空时slow恰好落在待删除节点的前驱上执行slow.next slow.next.next即可完成删除并返回dummy.next。对比两题可以发现从 dummy 出发让双指针间距多 1就能把定位节点转化为定位前驱这是链表删除类题目的关键技巧。小结返回倒数第 k 个节点LCCI 02.02是链表双指针的经典入门题其核心结论可以浓缩为一句话让快指针先行 k 步两指针同步前进快指针触底时慢指针即答案。doocs/leetcode 仓库为本题提供了中英文题解与八种语言的完整实现题解目录并借由剑指 Offer 22、剑指 Offer II 021 两个变式展示了同一套路在返回节点与删除节点场景下的演化。建议读者按通读题解 → 手写 Python 版本 → 对比 Rust/Swift 等语言特性差异 → 完成两个变式的顺序进行练习即可把快慢指针从会背模板提升为理解不动点。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点 本文基于 LeetCode Book 仓库中《剑指 Offer》第 22 题的解示例工程leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解 本文以本仓库的 19.removeNthNodeFromEn文档教程知识库ET框架事件驱动Buff系统设计3步解耦战斗逻辑ET框架事件驱动Buff系统设计3步解耦战斗逻辑 上一版本验收时某个Debuff加了一段层数叠加强制刷新结果UI血条、伤害飘字、成就判定三处依赖扣血流程的游戏开发后端微服务云原生上一篇Crossbeam与异步编程在Future中使用并发数据结构下一篇gh_mirrors/exam/examples开发技巧解决移动端模型加载速度慢的问题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
doocs/leetcode 题解精读：返回倒数第 k 个节点（LCCI 02.02）——快慢指针单趟遍历详解
示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 开源题解仓库中 《面试题 02.02. 返回倒数第 k 个节点》 的官方题解为核心完整讲解单向链表倒数第 k 个节点问题的快慢指针解法并覆盖 Python、Java、C、Go、TypeScript、Rust、JavaScript、Swift 八种语言的实现细节。读完本文你将掌握一趟扫描 常数空间定位链表倒数第 k 个节点的通用套路并能在仓库内同类题目剑指 Offer 22、剑指 Offer II 021中举一反三。题目背景与问题描述本题来自《程序员面试金典第 6 版》第 2 章链表部分题目编号02.02在仓库中的完整题解位于 lcci/02.02.Kth Node From End of List/README.md。题目要求实现一种算法找出单向链表中倒数第 k 个节点返回该节点的值。示例输入1 - 2 - 3 - 4 - 5 和 k 2 输出4两个重要说明注意本题相对原书题目稍作改动。原书CTCI 2.2通常要求返回倒数第 k 个节点这个节点本身而本题改为返回该节点的值函数签名也相应变为kthToLast(head, k) - int给定的 k 保证是有效的即满足1 ≤ k ≤ nn 为链表长度因此在官方题解中不需要对 k 做合法性校验也无需在链长为 0 时做空指针兜底。解法核心快慢指针方法一思路推导直观思路是把倒数转化为正数倒数第 k 个节点等价于正数第n - k 1个节点。由此得到最朴素的两趟遍历方案第一趟扫描链表统计长度 n第二趟从头走n - k步即可定位目标节点。该方案正确且 n 通常不大但题目希望一趟遍历完成。观察到一个关键性质若快指针比慢指针提前 k 步那么当快指针抵达链表末尾null时慢指针恰好停在倒数第 k 个节点上。这正是快慢指针双指针解法的核心思想——把未知的链表长度这个信息转化为两指针之间的固定步距从而无需预先知道 n。算法步骤定义两个指针slow和fast初始时都指向链表头节点headfast指针先向前移动 k 步然后slow与fast指针同时向前移动每次各走一步直到fast指针指向链表末尾为空时停止此时slow指针指向的节点就是倒数第 k 个节点返回slow.val。整个过程只扫描链表一次时间复杂度 O(n)其中 n 是链表的长度全程只使用两个指针变量空间复杂度 O(1)。示例逐步推演以1 - 2 - 3 - 4 - 5、k 2为例步骤fast 指向slow 指向说明初始化节点 1节点 1两指针同起于头节点fast 走第 1 步节点 2节点 1fast 先行fast 走第 2 步节点 3节点 1fast 共领先 k2 步同步前进 1节点 4节点 2两指针间距保持 2同步前进 2节点 5节点 3两指针间距保持 2同步前进 3null末尾节点 4fast 为空循环结束循环结束时slow指向节点 4即倒数第 2 个节点与题目输出一致。八种语言实现详解以下实现均继承自官方题解并与仓库中对应的 Solution 文件保持一致。读者可在 lcci/02.02.Kth Node From End of List 目录下查看各语言的独立源文件。Python3对应源文件Solution.pyclass Solution: def kthToLast(self, head: ListNode, k: int) - int: slow fast head for _ in range(k): fast fast.next while fast: slow slow.next fast fast.next return slow.valfor _ in range(k)让fast先行 k 步随后while fast以fast是否为None作为终止条件循环结束后直接返回slow.val简洁直观。Java对应源文件Solution.javaclass Solution { public int kthToLast(ListNode head, int k) { ListNode slow head, fast head; while (k-- 0) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; } }利用k-- 0的后置自减写法把走 k 步压缩为一行循环第二个while以fast ! null为循环条件语义与 Python 版本完全对应。C对应源文件Solution.cppclass Solution { public: int kthToLast(ListNode* head, int k) { ListNode* fast head; ListNode* slow head; while (k--) { fast fast-next; } while (fast) { slow slow-next; fast fast-next; } return slow-val; } };C 版本使用原生指针while (k--)依赖k递减到 0 时退出第二个循环以指针本身非空即真作为条件与 Go 的写法习惯相近。Go对应源文件Solution.gofunc kthToLast(head *ListNode, k int) int { slow, fast : head, head for ; k 0; k-- { fast fast.Next } for fast ! nil { slow slow.Next fast fast.Next } return slow.Val }Go 版本用for ; k 0; k--显式控制步数第二个循环以fast ! nil终止语义清晰注意 Go 中字段名为Val、Next首字母大写。TypeScript对应源文件Solution.tsfunction kthToLast(head: ListNode | null, k: number): number { let [slow, fast] [head, head]; while (k--) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; }TypeScript 版本用解构赋值let [slow, fast] [head, head]一次性初始化两个指针并在类型层面显式标注head: ListNode | null在k保证有效的前提下fast.next与slow.val的访问是安全的。Rust对应源文件Solution.rsimpl Solution { pub fn kth_to_last(head: OptionBoxListNode, k: i32) - i32 { let mut fast head; for _ in 0..k { fast fast.as_ref().unwrap().next; } let mut slow head; while let (Some(f), Some(s)) (fast, slow) { fast f.next; slow s.next; } slow.as_ref().unwrap().val } }Rust 版本最能体现语言特性链表以OptionBoxListNode表示fast、slow均为对head的不可变引用。fast.as_ref().unwrap().next在先行阶段逐层取得下一节点的引用同步阶段通过while let (Some(f), Some(s))同时解构两个引用并前进最终slow.as_ref().unwrap().val取出目标值。整个过程零拷贝、零所有权转移充分说明快慢指针算法在所有权严格的语言中同样可以优雅落地。JavaScript对应源文件Solution.jsvar kthToLast function (head, k) { let [slow, fast] [head, head]; while (k--) { fast fast.next; } while (fast ! null) { slow slow.next; fast fast.next; } return slow.val; };JavaScript 与 TypeScript 的实现几乎一致仅少类型标注while (k--)的写法在k递减为 0 时自动退出循环。Swift对应源文件Solution.swiftclass Solution { func kthToLast(_ head: ListNode?, _ k: Int) - Int { var slow head var fast head var k k while k 0 { fast fast?.next k - 1 } while fast ! nil { slow slow?.next fast fast?.next } return slow?.val ?? 0 } }Swift 版本使用可选链fast?.next遍历fast为ListNode?并对入参k做了局部拷贝var k k以便递减返回时用slow?.val ?? 0对可选值兜底——在 k 保证有效的前提下实际取值必然是目标节点的值。仓库源码佐证与题解组织方式doocs/leetcode 仓库对每道题的组织遵循统一约定每个题目目录下包含README.md中文题解、README_EN.md英文题解以及按语言命名的独立 Solution 文件。以本题为例lcci/02.02.Kth Node From End of List 目录包含README.md —— 中文题解本文主体内容的来源README_EN.md —— 英文题解解法与中文版一一对应Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs、Solution.js、Solution.swift —— 共 8 个语言版本。需要特别说明的是lcci目录整体对应《程序员面试金典第 6 版》题号02.02中的02代表第 2 章链表。仓库中同一算法思想还以不同变体出现在多个目录中这正是我们下一节要展开的内容。算法正确性与复杂度论证为什么慢指针最终一定落在倒数第 k 个节点设链表长度为 n。当fast先走完 k 步后slow仍在头节点两指针间距恒为 k。此后两指针每次同步前进一步间距保持不变。当fast走到末尾null时它从起点共走了 n 步链表共有 n 个节点从第 1 个节点走到 null 需要 n 步而slow比fast少走 k 步共走了n - k步恰好落在正数第n - k 1个节点上——这正是倒数第 k 个节点。复杂度时间复杂度 O(n)fast先行 k 步、随后两指针同步前进合计恰好遍历一遍链表空间复杂度 O(1)仅使用两个指针变量不依赖链表长度。相比两趟遍历方案先数长度、再走n - k步快慢指针在渐进复杂度同为 O(n) 的前提下把扫描压缩为一趟常数更小也是面试中更受青睐的写法。边界情况讨论由于题目保证k有效1 ≤ k ≤ n官方实现无需额外保护但理解边界仍有助于加深对算法不动点的把握k 1尾节点fast先行 1 步后两指针同步前进当fast到达 null 时slow恰好位于最后一个节点返回尾节点值k n头节点fast先行 n 步后直接为 null第二个循环一次都不执行slow仍指向头节点返回头节点值若题目不保证 k 有效如k n或链表为空上述实现会在先行阶段对fast解引用空指针而崩溃此时需要先校验长度或增加空指针判断——这是实战中需要根据题目约束灵活调整的地方。仓库内同类题目的变式延伸快慢指针解决倒数第 k类问题的套路在 doocs/leetcode 仓库中还有两个典型变式可作为练习与对比变式一剑指 Offer 22 —— 返回节点而非值《面试题 22. 链表中倒数第 k 个节点》 与本题算法骨架完全一致唯一区别是返回类型该题要求返回倒数第 k 个节点本身ListNode*而本题返回int值。对比两个版本的函数签名与返回语句可以清晰看到同一算法在不同接口约束下的适配方式。变式二剑指 Offer II 021 —— 删除倒数第 n 个结点《剑指 Offer II 021. 删除链表的倒数第 n 个结点》 把定位升级为定位并删除。删除操作需要访问目标节点的前驱因此该题引入哨兵节点dummy ListNode(nexthead)让slow、fast都从dummy出发fast先行n 1步同步前进直到fast为空时slow恰好落在待删除节点的前驱上执行slow.next slow.next.next即可完成删除并返回dummy.next。对比两题可以发现从 dummy 出发让双指针间距多 1就能把定位节点转化为定位前驱这是链表删除类题目的关键技巧。小结返回倒数第 k 个节点LCCI 02.02是链表双指针的经典入门题其核心结论可以浓缩为一句话让快指针先行 k 步两指针同步前进快指针触底时慢指针即答案。doocs/leetcode 仓库为本题提供了中英文题解与八种语言的完整实现题解目录并借由剑指 Offer 22、剑指 Offer II 021 两个变式展示了同一套路在返回节点与删除节点场景下的演化。建议读者按通读题解 → 手写 Python 版本 → 对比 Rust/Swift 等语言特性差异 → 完成两个变式的顺序进行练习即可把快慢指针从会背模板提升为理解不动点。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点 本文基于 LeetCode Book 仓库中《剑指 Offer》第 22 题的解示例工程leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解leetcode 题解19. 删除链表的倒数第 N 个节点 —— 双指针 虚拟头一次遍历详解 本文以本仓库的 19.removeNthNodeFromEn文档教程知识库ET框架事件驱动Buff系统设计3步解耦战斗逻辑ET框架事件驱动Buff系统设计3步解耦战斗逻辑 上一版本验收时某个Debuff加了一段层数叠加强制刷新结果UI血条、伤害飘字、成就判定三处依赖扣血流程的游戏开发后端微服务云原生上一篇Crossbeam与异步编程在Future中使用并发数据结构下一篇gh_mirrors/exam/examples开发技巧解决移动端模型加载速度慢的问题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
