第4章｜链表
Unit 06 · 快慢指针：速度差如何定位中点
快指针不是“更快地找答案”，
而是在移动过程中编码位置比例。
当 fast 每轮走两步、slow 每轮走一步时，fast 到达链表末端的那一刻，slow 恰好走完一半路径。奇数链表返回唯一中点；偶数链表按题意返回第二个中间结点。
检测到上次学习进度可以恢复到离开前的阶段、动画、代码和滚动位置。
LeetCode #876 题目模型Middle of the Linked List · Easy
题目要求
给定一个非空单链表的头结点 head，返回链表的中间结点。若有两个中间结点，则返回第二个中间结点。
class Solution:
def middleNode(
self,
head: Optional[ListNode]
) -> Optional[ListNode]:
pass
输入、输出与约束
- 节点数量在
[1, 100]范围内； - 节点值在
[1, 100]范围内； - 输出是中间节点对象，而不是节点值或索引。
示例
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：节点 3 是唯一中间结点。
输出：[3,4,5]
解释：节点 3 是唯一中间结点。
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：两个中间结点为 3 和 4，返回第二个节点 4。
输出：[4,5,6]
解释：两个中间结点为 3 和 4，返回第二个节点 4。
复杂度目标
一次扫描，时间复杂度 O(n)；只使用两个节点指针，额外空间复杂度 O(1)。
与 Unit 05 的联系：继续让“运动关系”代替提前计数
Unit 05：固定距离
fast 先走 n+1 步，再与 slow 同速移动；末端事件定位倒数节点前驱。
→
Unit 06：固定速度比
fast 每轮走 2 步，slow 每轮走 1 步；末端事件定位链表长度的一半。
Slow Pointer
每轮移动一步。算法结束时，它承担返回中点的职责。
Fast Pointer
每轮移动两步。它通过先到达末端来提供“链表已走完”的事件。
Speed Ratio
快慢速度比为 2:1，因此 fast 走完整条链时，slow 走到一半。
Second Middle
偶数长度存在两个中间节点；循环条件使 slow 停在第二个中间节点。
链表与指针动画节点位置不变，指针按真实 next 边移动
slow—
fast—
slow 步数0
fast 步数0
当前结论未确定
Observe
Check
slow +1
fast +2
Return slow
当前状态契约每一步都回答“为什么 slow 在这里”
核心不变量
每完成一轮循环，fast 走过的边数是 slow 的两倍；所有已经经过的 next 边都没有被修改。
循环条件fast and fast.next
终止事件fast 到达 None 或 fast.next 到达 None
返回语义返回 slow 节点对象
节点访问量0
额外空间O(1)
奇偶长度的统一处理
奇数长度
fast 最终停在最后节点；slow 位于唯一中点。
fast 最终停在最后节点；slow 位于唯一中点。
偶数长度
fast 最终到达 None；slow 位于第二中点。
fast 最终到达 None；slow 位于第二中点。
补全可直接提交的 Python 代码只填关键表达式
from typing import Optional
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow =
fast =
while :
slow =
fast =
return
必须正确补全代码，或完整播放执行轨迹，才能解锁迁移。提示和初始化骨架不会提前解锁。
代码—指针—链表逐行联动点击代码行可跳转到对应状态
slow—
fast—
返回未返回
链表长度5
slow 步数0
fast 步数0
完成代码联动后进入 #143《重排链表》迁移先用本题定位分割点，再复用 Unit 02 反转后半段，最后新增交替合并。
迁移题：LeetCode #143《重排链表》
这次不再重复 #234。#143 要求把三个 Skill 串成一条不可打乱的执行链：找中点、断开并反转后半段、交替合并两段。迁移过程不会直接给出完整答案。
Unit 06 Skill 卡：用速度关系编码位置比例
完成本单元后，你应该不再把快慢指针理解成“两个移动速度不同的变量”，而应把它看作一个不需要提前知道长度的位置测量器。
触发信号需要找到中点或按比例定位
核心表示slow 每轮 1 步，fast 每轮 2 步
不变量fast 走过边数 = 2 × slow
终止条件fast is None 或 fast.next is None
偶数定义返回第二个中间结点
迁移方向重排链表：中点 + 反转 + 交替合并
本页不会自动跳转可以继续复看任何阶段；准备好后再手动进入 Unit 07「环形链表」。
手动进入 Unit 07 →