257 字
1 分钟
快慢指针寻找中间节点算法笔记
在链表问题中，经常需要找到链表的 中间节点。 最常见的方法是 快慢指针。
核心思想：
slow每次走 1步fast每次走 2步
当 fast 走到链表末尾时：
slow 正好在中间一、基本原理
初始化两个指针：
slow = headfast = head循环移动：
while fast and fast.next: slow = slow.next fast = fast.next.next最终：
slow 指向链表中间节点二、图示理解（奇数链表）
链表：
1 → 2 → 3 → 4 → 5初始状态：
slow↓1 → 2 → 3 → 4 → 5↑fast第一轮移动：
slow ↓1 → 2 → 3 → 4 → 5 ↑ fast第二轮移动：
slow ↓1 → 2 → 3 → 4 → 5 ↑ fast结束：
slow ↓1 → 2 → 3 → 4 → 5
fast → None最终：
slow = 3中间节点是 3。
三、代码模板
def middleNode(head):
slow = head fast = head
while fast and fast.next: slow = slow.next fast = fast.next.next
return slow复杂度：
时间复杂度：O(n)空间复杂度：O(1)四、偶数链表情况
链表：
1 → 2 → 3 → 4移动过程：
初始：
slow↓1 → 2 → 3 → 4↑fast第一轮：
slow ↓1 → 2 → 3 → 4 ↑ fast第二轮：
slow ↓1 → 2 → 3 → 4
fast → None最终：
slow = 3返回 右中点。
五、典型应用场景
快慢指针是链表题的 核心技巧，常用于：
1 回文链表
1 → 2 → 3 → 2 → 1 ↑ 中点步骤：
1 找中点2 反转后半链表3 比较2 归并排序链表
1 → 4 → 3 → 2 → 5拆成：
1 → 4 → 32 → 53 判断链表是否有环
Floyd 判环算法：
slow 每次1步fast 每次2步如果：
slow == fast说明链表有环。
六、核心总结
快慢指针的本质：
fast 速度 = slow × 2当：
fast 到达终点则：
slow 位于中点部分信息可能已经过时