§1
题目描述
给定单链表头结点 head,返回中间结点。若有两个中间结点,返回第二个。
输入 = 1→2→3→…→9 输出 = 5(下标 4)
§2
思路解析动画文字版
记住这条比例:fast 是 slow 的两倍速。
出发:slow、fast 都站在头结点(下标 0)。
第 1 轮:slow 向前走 1 格,到下标 1。
同一轮:fast 向前走第 1 格,到下标 1。
fast 再走 1 格(这轮共走 2 格),到下标 2。此刻 fast 跑在 slow 前面整整一倍距离。
第 2 轮:slow 向前走 1 格,到下标 2。
同一轮:fast 向前走第 1 格,到下标 3。
fast 再走 1 格(这轮共走 2 格),到下标 4。此刻 fast 跑在 slow 前面整整一倍距离。
第 3 轮:slow 向前走 1 格,到下标 3。
同一轮:fast 向前走第 1 格,到下标 5。
fast 再走 1 格(这轮共走 2 格),到下标 6。此刻 fast 跑在 slow 前面整整一倍距离。
第 4 轮:slow 向前走 1 格,到下标 4。
同一轮:fast 向前走第 1 格,到下标 7。
fast 再走 1 格(这轮共走 2 格),到下标 8。此刻 fast 跑在 slow 前面整整一倍距离。
fast 再走 2 格就出链了(next 为空),循环停止。slow 停在下标 4 —— 正好是中点,即第 5 个结点,就是答案。
边界先想清楚。
两个高频追问。
§3
参考代码
def middleNode(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间:O(n),fast 一遍走完即停
- 空间:O(1),只用两个指针
§5
易错点
✗ 错误写法:while 写成 fast.next && fast
✓ 正确写法:fast 在前:先判 fast 非空再访问 fast.next
顺序反了 fast 为空时访问 .next 会崩
✗ 错误写法:偶数返回了第一个中点
✓ 正确写法:slow=fast=head 起步 → 偶数自然返回第二个
本题要求返回靠后的那个
✗ 错误写法:先遍历数长度再走一半
✓ 正确写法:快慢指针一次搞定
两次遍历多余,快慢指针更优雅
§
面试追问把动画讲成自己的话
追问快慢指针还能解什么?
判断链表有无环(fast 追上 slow 即有环)、找环入口、找倒数第 k 个结点等。
追问为什么 fast 到尾 slow 正好一半?
fast 速度是 slow 两倍,走过的距离也是两倍;fast 走完全程 n,slow 自然走了 n/2。
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 链表套路 9/44
→二进制链表转整数
LeetCode 1290 · 简单 · 沿着 链表套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
899道动画图解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题