文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载导读在算法刷题与面试中链表是最基础也最高频的考点之一。本文以 algorithm-base 仓库中 面试题 02.03. 链表中间节点 为主体深入讲解如何用快慢指针Floyd 龟兔赛跑思想在一次遍历、O(1) 额外空间内找到单链表的中间节点并与仓库中倒数第 k 个节点、环形链表、回文链表 等经典题目串成一条链表双指针知识线。读完本文你将掌握快慢指针的推导思路、奇偶长度边界处理以及中间节点在后续复杂题目中的复用价值。一、题目描述给定一个头结点为head的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。示例 1输入[1,2,3,4,5] 输出节点 3说明因为只有一个中间节点。示例 2输入[1,2,3,4,5,6] 输出节点 4说明有两个中间节点所以返回后面那个。该题对应力扣 876. 链表的中间结点同时也是《程序员面试金典》面试题 02.03可见其经典程度。前提约束链表非空因此无需处理head null的空链表边界但链表长度可为奇数或偶数这直接影响循环条件的设计下文会重点分析。二、由浅入深的三种思路推演拿到题目后先不急着看题解可以按下面三个阶段自我推演1. 两次遍历法最容易想到第一次遍历链表统计节点总数n第二次遍历走到第n / 2 1个节点注意是第二个中间节点所以取n/2的下一个即为答案。时间复杂度O(n)空间复杂度O(1)。缺点需要两次遍历链表越长代价越明显。2. 数组辅助法空间换时间利用数组将所有链表元素先存入再直接通过索引取得中间节点ListNode[] arr ...; // 顺序存储所有节点 return arr[arr.length / 2];时间复杂度O(n)空间复杂度O(n)。缺点需要额外辅助空间在只允许常数级额外空间的约束下不满足要求。3. 快慢指针法一次遍历零辅助空间这正是本文的主角。上面的思路推演在仓库原文中也有完整铺垫见 面试题 02.03. 链表中间节点。三、快慢指针核心思想与动画解读1. 思路来源与倒数第 k 个节点的联系在仓库的剑指 offer 22 链表中倒数第 k 个节点 中我们使用一前一后双指针两个指针之间始终相差k - 1位当前指针到达链表尾部时后指针恰好指向倒数第 k 个节点。中间节点问题可以看作这个思想的一个变体我们不需要两个指针保持固定间距而是让一个指针走得快、一个指针走得慢——这种快慢双指针正是链表题目的高频套路被称作快慢指针fast-slow pointer。2. 算法过程快指针fast每次走两步fast fast.next.next慢指针slow每次走一步slow slow.next当快指针到达链表尾部时慢指针恰好位于链表中间。3. 奇偶长度的两种情形链表中节点个数可能为奇数也可能为偶数这是本题最核心的边界链表长度示例循环终止条件触发点慢指针落点奇数如 5 个节点1→2→3→4→5fast.next null正中间节点 3偶数如 6 个节点1→2→3→4→5→6fast null第二个中间节点 4关键点两种情况下我们输出的都是slow指针指向的节点即两个中间节点的第二个。为什么会这样因为循环条件写成while (fast ! null fast.next ! null)奇数长度fast最终停在最后一个节点fast.next null此时slow移动了(n-1)/2步正好落在中间偶数长度fast最终越界为null此时slow移动了n/2步落在第n/2 1个节点也就是第二个中间节点。这一取第二个中间节点的约定与力扣题目要求完全一致。仓库原文配有一张 CSDN 上的动画模拟图20210321131249789.gif形象地展示了快慢指针的推进过程建议读者结合动画自行在纸上推演一遍。四、题目代码六种语言实现仓库原文给出了 Java、C、JS、Python、Swift、Go 六种语言的完整实现全部保持同一套循环条件逻辑可直接复制运行Javaclass Solution { public ListNode middleNode(ListNode head) { ListNode fast head;//快指针 ListNode slow head;//慢指针 //循环条件思考一下跳出循环的情况 while (fast!null fast.next ! null) { fast fast.next.next; slow slow.next; } //返回slow指针指向的节点 return slow; } }Cclass Solution { public: ListNode* middleNode(ListNode* head) { ListNode * fast head;//快指针 ListNode * slow head;//慢指针 //循环条件思考一下跳出循环的情况 while (fast ! nullptr fast-next ! nullptr) { fast fast-next-next; slow slow-next; } //返回slow指针指向的节点 return slow; } };JavaScriptvar middleNode function (head) { let fast head; //快指针 let slow head; //慢指针 //循环条件思考一下跳出循环的情况 while (fast fast.next) { fast fast.next.next; slow slow.next; } //返回slow指针指向的节点 return slow; };Pythonclass Solution: def middleNode(self, head: ListNode) - ListNode: fast head # 快指针 slow head # 慢指针 # 循环条件思考一下跳出循环的情况 while fast is not None and fast.next is not None: fast fast.next.next slow slow.next # 返回slow指针指向的节点 return slowSwiftclass Solution { func middleNode(_ head: ListNode?) - ListNode? { var fast head //快指针 var slow head //慢指针 //循环条件思考一下跳出循环的情况 while fast ! nil fast?.next ! nil { fast fast?.next?.next slow slow?.next } //返回slow指针指向的节点 return slow } }Gofunc middleNode(head *ListNode) *ListNode { // 快慢指针 fast, slow : head, head for fast ! nil fast.Next ! nil { fast fast.Next.Next slow slow.Next } return slow }复杂度分析时间复杂度O(n)快慢指针各遍历链表一次整体只扫描一遍快指针步长 2总步数约为 n/2空间复杂度O(1)仅使用两个指针变量未开辟任何辅助容器。五、快慢指针知识线与仓库源码佐证1. ListNode 节点的定义约定仓库在 Leetcode常用类和函数.md 中给出了刷题常用的ListNode初始化写法ListNode list new ListNode(0);即每个链表节点持有val与next引用构成链式结构。上面六种语言的middleNode均以该结构为前提。2. 同类题一链表中倒数第 k 个节点固定间距双指针在 剑指offer22倒数第k个节点.md 中算法思想是一个指针先移动k-1位然后两个指针同速移动、始终保持相差 k-1 位当前指针到达链表尾部时后指针指向倒数第 k 个节点。对比可知题目两指针关系终止条件返回值倒数第 k 个节点固定相差k-1位、同速前指针到尾部后指针中间节点快指针速度是慢指针的 2 倍快指针到尾部/越界慢指针两者都是用指针位移关系定位链表位置的经典应用建议放在一起对比学习。3. 同类题二环形链表快慢指针追及在 leetcode141环形链表.md 中同样使用快慢指针快指针一次走两步、慢指针一次走一步若链表有环快指针若干圈后必然追上慢指针fast slow即为有环证据。while (fast ! null fast.next ! null) { fast fast.next.next; slow slow.next; if (fast slow) return true; }可以看到循环条件与本题完全一致——这说明快指针每次跳两步 判空保护是快慢指针在单链表上的通用骨架理解本题后即可无缝迁移到环形检测场景。4. 进阶应用回文链表中间节点的实战价值中间节点最大的实战价值体现在复合题目中。234. 回文链表.md 给出了一个非常典型的组合套路先找到中间节点searchmidnode翻转后半段链表reverse双指针遍历前后两半比较值判断是否为回文结束后再翻转一次还原链表原始结构。值得注意的是回文链表中需要的是第一个中间节点因此其查找函数用了不同的循环条件public ListNode searchmidnode (ListNode head) { ListNode fast head; ListNode slow head; while (fast.next ! null fast.next.next ! null) { fast fast.next.next; slow slow.next; } return slow; }对比本题的while (fast ! null fast.next ! null)仅一处条件不同返回的中间节点就从第二个变成了第一个。这恰好印证了仓库原文的提示如果有两个中间节点返回第一个昨天的题目是第二个。两篇文档对照阅读可以彻底吃透中间节点两种取法背后的循环条件差异。六、易错点与面试延伸1. 循环条件为什么必须判fast ! null fast.next ! null若只判fast ! null偶数长度时fast会在倒数第二个节点先走fast.next.next得到null下一次循环再访问fast.next会触发空指针异常若只判fast.next ! null当fast已为null时访问fast.next同样报错。所以两个条件缺一不可顺序上先判fast ! null保证fast.next可安全访问再判fast.next ! null保证fast.next.next可安全访问。2. 返回第二个中间节点的含义题目明确约定偶数长度下返回两个中间节点的后一个。例如[1,2,3,4,5,6]返回节点 4。若题目改为返回第一个中间节点只需把循环条件换成fast.next ! null fast.next.next ! null见上节回文链表写法。3. 面试加分项不修改链表结构在回文链表等复合题中翻转后半段后务必再次翻转还原以保持输入链表结构不被破坏仓库原文在 234. 回文链表.md 中对此有明确注释我们不可以破坏初始结构。中间节点定位本身不改动任何指针指向天然安全。七、总结链表中间节点看似简单却是快慢指针体系的题眼所在掌握一次遍历、O(1) 空间的快慢指针解法理解奇偶长度下循环条件与返回节点的关系能够将中间节点作为子步骤复用到回文链表、链表重排如 leetcode 143、奇偶链表等进阶题目中。建议结合仓库中 面试题 02.03. 链表中间节点 原文的动画以及倒数第 k 个节点、环形链表、回文链表、反转链表 四篇姊妹篇把链表双指针这一族题目一次性打通。赞分享文档教程知识库【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址https://gitcode.com/gh_mirrors/al/algorithm-base点击查看免费下载相关推荐剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点剑指 Offer 22 精讲用快慢双指针一次遍历找到链表中倒数第 k 个节点 本文基于 LeetCode Book 仓库中《剑指 Offer》第 22 题的解示例工程LeetCode 141 环形链表algorithm-base 动画模拟用快慢指针判定链表是否成环LeetCode 141 环形链表algorithm base 动画模拟用快慢指针判定链表是否成环 本篇技术指南来自 algorithm base 仓库的文档教程知识库ToolJet Bounded Box 组件实战图像标注、目标框选与 ML 数据集构建指南ToolJet Bounded Box 组件实战图像标注、目标框选与 ML 数据集构建指南 Bounded Box 是 ToolJet 中用于图像标注的可视化文档教程知识库上一篇在Android手机运行Windows应用Mobox让你的手机变身移动电脑下一篇Get Shit Done突破性AI编程上下文工程系统彻底解决Claude Code质量衰退难题创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
