快慢指针法深度解析：解决链表环、中点、倒数第K节点3类问题的统一思路
链表操作是算法面试中的高频考点，而快慢指针法则是解决链表问题的利器。本文将深入剖析快慢指针的核心思想，展示如何用这一技巧优雅解决链表环检测、寻找中点、定位倒数第K节点这三类经典问题。
1. 快慢指针法的基本原理
快慢指针（Fast-Slow Pointers）是一种通过两个指针以不同速度遍历链表来解决问题的技巧。其核心在于：
- 快指针：每次移动两步（
fast = fast->next->next） - 慢指针：每次移动一步（
slow = slow->next）
这种速度差会产生以下关键特性：
当快指针到达链表末尾时，慢指针正好位于链表中间位置。这个特性是解决多种链表问题的基础。
快慢指针的通用代码模板如下：
ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; // 根据具体问题在此添加判断逻辑 }2. 链表环检测与入口定位
2.1 环检测原理
当链表存在环时，快指针最终会追上慢指针（类似于环形跑道上的运动员）：
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数学证明：设环外长度为L，环长为C。当慢指针进入环时，快指针已在环中移动L步（距离慢指针C-L%c）。由于每步距离差1，经过C-L%c次移动后两指针必然相遇。
2.2 环入口定位算法
找到相遇点后，将其中一个指针移回头部，两指针同速移动，再次相遇点即为环入口：
public ListNode detectCycle(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; }3. 链表中点查找的变体与应用
3.1 基础中点查找
快指针到达末尾时，慢指针即为中点：
| 链表长度 | 中点位置 |
|---|---|
| 奇数 | 正中间 |
| 偶数 | 靠右节点 |
ListNode* middleNode(ListNode* head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }3.2 进阶应用：回文链表判断
结合反转链表技巧：
- 找到中点
- 反转后半部分
- 比较前后两部分
def isPalindrome(head): # 找中点 slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next # 反转后半部分 prev = None while slow: tmp = slow.next slow.next = prev prev = slow slow = tmp # 比较 left, right = head, prev while right: if left.val != right.val: return False left = left.next right = right.next return True4. 倒数第K个节点的快慢指针解法
传统解法需要两次遍历，快慢指针可实现一次遍历：
- 快指针先走K步
- 两指针同步移动直至快指针到达末尾
public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head, slow = head; while (k-- > 0) { fast = fast.next; } while (fast != null) { slow = slow.next; fast = fast.next; } return slow; }边界条件处理：
- K超过链表长度时返回头节点
- K=0时返回null
- 空链表直接返回null
5. 性能对比与工程实践
三种问题的性能对比：
| 问题类型 | 时间复杂度 | 空间复杂度 | 快慢指针适用性 |
|---|---|---|---|
| 环检测 | O(n) | O(1) | ★★★★★ |
| 中点查找 | O(n) | O(1) | ★★★★★ |
| 倒数第K节点 | O(n) | O(1) | ★★★★☆ |
实际编码中的常见陷阱：
- 快指针移动时需要先检查
fast.next是否为空 - 处理偶数长度链表时中点的选择（左或右）
- K值校验避免越界访问
// 安全的快指针移动写法 while (fast && fast->next) { // 双重检查 fast = fast->next->next; // 移动两步 // ... }6. 综合应用案例：链表重排序
结合中点查找和反转操作，实现L0→Ln→L1→Ln-1...的重排序：
def reorderList(head): if not head or not head.next: return # 找中点 slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next # 反转后半部分 prev, curr = None, slow.next slow.next = None while curr: tmp = curr.next curr.next = prev prev = curr curr = tmp # 合并 first, second = head, prev while second: tmp1, tmp2 = first.next, second.next first.next = second second.next = tmp1 first, second = tmp1, tmp2这个案例完美展示了快慢指针在中点查找中的关键作用，以及如何与其他链表操作组合解决复杂问题。
