核心：快慢指针法通过设置两个同向移动但速度不同的指针，解决链表中的环检测、中点查找、重排等问题。其本质是利用相对运动特性，让两指针在特定条件下相遇。
一、基础知识点
1. 链表中点查找（快慢指针基础）
问题定义
给定单链表，找到链表的中间节点：
奇数长度链表（如 1→2→3→4→5）返回中间节点 3
偶数长度链表（如 1→2→3→4）返回第二个中间节点 4
暴力解法
先遍历一遍链表得到长度 n，时间 O(n)
再遍历到第 n/2 个节点，空间 O(1)
总时间 O(n)，空间 O(1)
优化解法（快慢指针）
设置两个指针：
慢指针 (slow)：每次走 1 步
快指针 (fast)：每次走 2 步
当快指针到达链表末尾时，慢指针恰好在中间位置。
循环终止条件证明
奇数长度：快指针到达最后一个节点时，其下一个为空，退出循环，此时慢指针在中间
偶数长度：快指针到达空节点时退出，此时慢指针在第二个中间节点
复杂度
时间：O(n)，快指针遍历完整个链表
空间：O(1)，仅用两个指针变量
Python 实现
def middleNode(head):
# 初始化快慢指针均指向头节点
slow = fast = head
# 循环终止条件：快指针为空或快指针的下一个为空
while fast and fast.next:
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
# 此时 slow 指向中间节点
return slow
2. 环形链表检测（LeetCode 141）
题目描述
给定一个链表，判断链表中是否有环。要求空间复杂度为 O(1)。
核心思路
快指针每次走 2 步，慢指针每次走 1 步
若链表中有环，快慢指针必然在环内相遇（类似追及问题）
若链表中无环，快指针会先到达链表尾部
相对速度分析
在环中，快指针相对慢指针的相对速度为 1 步 / 循环，因此快指针一定能追上慢指针。
复杂度
时间：O(n)，慢指针进入环后，最多遍历环长 n 步就会相遇
空间：O(1)
Python 实现
def hasCycle(head):
slow = fast = head # 快慢指针初始化
while fast and fast.next:
slow = slow.next # 慢指针走一步
fast = fast.next.next # 快指针走两步
if slow == fast: # 两指针相遇，说明有环
return True
return False # 快指针到达末尾，无环
3. 环形链表 II - 找环入口（LeetCode 142）
题目描述
给定一个链表，返回链表中环的入口节点。若链表无环，返回 null。
核心概念
设从链表头到环入口的距离为 A，入口到相遇点的距离为 B，相遇点到入口的距离为 C。
环长 = B + C
慢指针移动距离 = A + B
快指针移动距离 = A + B + k(B + C)（k ≥ 1）
数学推导
由于快指针速度是慢指针的 2 倍：
2(A + B) = A + B + k(B + C)
A + B = k(B + C)
A = (k - 1)B + kC
当 k = 1 时：A = C
即：从相遇点出发走 C 步到达入口，从头节点出发走 A 步也到达入口。
算法步骤
快慢指针同时出发，快指针速度为慢指针的 2 倍
两指针相遇后，将其中一个指针重置到头节点
两指针以相同速度（每次各走一步）继续前进
再次相遇的位置即为环的入口
为什么慢指针未走完一圈？
最坏情况：慢指针刚进入环时，快指针恰好在慢指针前方一步。此时快指针需要追及的距离为 (B + C - 1)，不超过环长。因此慢指针最多走 B + C - 1 < 环长，不会走完一整圈。
复杂度
时间：O(n)，第一阶段相遇最多 O(n)，第二阶段从入口到相遇最多 O(n)
空间：O(1)
Python 实现
def detectCycle(head):
slow = fast = head
# 阶段1：找到快慢指针的相遇点
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
# 无环情况
if not fast or not fast.next:
return None
# 阶段2：找环入口
# 将 slow 重置到头节点，fast 保持在相遇点
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # 环入口节点
二、练习题目
1. 234. 回文链表 📐
题目描述
给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。
示例
输入：head = [1,2,2,1]
输出：true
解释：链表正着读和反着读一样，是回文链表。
解题思路
第一步：找到链表的中间节点（快慢指针）
第二步：反转中间节点之后的链表
第三步：双指针比较：头节点到中间 vs 反转后的链表，逐节点比较值是否相等
复杂度
时间：O(n)，三次遍历（找中点 O(n/2) + 反转 O(n/2) + 比较 O(n/2)）
空间：O(1)
Python 代码
class Solution:
def middleNode(self, head):
"""快慢指针找中间节点"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head):
"""反转链表：pre指向已反转部分，cur指向未反转部分"""
pre, cur = None, head
while cur:
nxt = cur.next # 保存下一个节点
cur.next = pre # 反转当前节点的指向
pre = cur # pre 前进到当前节点
cur = nxt # cur 前进到下一个节点
return pre
def isPalindrome(self, head):
mid = self.middleNode(head) # 找到中间节点
head2 = self.reverseList(mid) # 反转后半部分链表
while head2: # 逐节点比较
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
2. 2130. 链表最大孪生和 🎯
题目描述
在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n/2) - 1 的 i：
第
i个节点的孪生节点为第(n - 1 - i)个节点孪生和 = 节点值 + 其孪生节点值
给你链表的头节点，返回链表的最大孪生和。
示例
输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 3 是孪生节点，孪生和 = 5 + 1 = 6
节点 1 和节点 2 是孪生节点，孪生和 = 4 + 2 = 6
最大孪生和为 6
解题思路
与回文链表类似：
快慢指针找中点
反转后半部分链表
双指针从两端向中间遍历，计算对应节点的孪生和，取最大值
复杂度
时间：O(n)
空间：O(1)
Python 代码
class Solution:
def middleNode(self, head):
"""快慢指针找中间节点"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(self, head):
"""反转链表"""
pre, cur = None, head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def pairSum(self, head):
mid = self.middleNode(head) # 找中点
head2 = self.reverseList(mid) # 反转后半部分
ans = 0
while head2: # 双指针遍历
ans = max(ans, head.val + head2.val) # 计算孪生和并取最大
head = head.next
head2 = head2.next
return ans
三、快慢指针解题总结 ✨
核心适用场景
链表中点查找 - 快指针走完时慢指针在中间
环形链表检测 - 快慢指针在环内相遇
环入口定位 - 数学推导证明两指针第二次相遇点即为入口
链表重排 - 结合找中点 + 反转链表
快慢指针模板
# 基础模板
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 此时 slow 指向中点（奇数）或第二个中点（偶数）
关键数学关系
复杂度速记
快慢指针找中点：时间 O(n)，空间 O(1)
环形检测：时间 O(n)，空间 O(1)
环形入口：时间 O(n)，空间 O(1)
结合反转链表：时间 O(n)，空间 O(1)
通用技巧
快指针每次走 2 步，是快慢指针的经典设置
无环一定终止：快指针先到达尾部
有环必定相遇：相对速度保证在环内追上
入口定位重置法：相遇后将任一指针重置到头，再次相遇即入口