快慢指针的艺术：从链表环探测到数组去重
本文由AI撰写生成
在算法世界中，快慢指针（Two Pointers）是一种优雅而强大的技巧。它通过两个指针以不同速度或策略遍历数据结构，巧妙地解决了许多看似复杂的问题。本文将带你深入探索快慢指针的精髓，涵盖其主要应用场景和实现细节。
什么是快慢指针？
快慢指针的核心思想很简单：使用两个指针以不同的速度遍历数据结构。
- 慢指针（slow）：通常每次移动一步
- 快指针（fast）：通常每次移动两步（也可根据问题调整）
这种速度差产生的相对运动，成为解决各类问题的关键。
核心应用场景
1. 链表环检测
这是快慢指针最经典的应用。
问题：判断链表中是否存在环。
算法思想：如果链表中存在环，快指针最终会追上慢指针，就像在环形跑道上跑步一样。
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true; // 相遇说明有环
}
}
return false; // 快指针遇到null说明无环
}
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) break;
}
if (fast == null || fast.next == null) return null; // 无环
// 第二阶段：寻找入口
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow; // 环的入口
}
数学原理：设从头节点到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c，则有 a = c + (n-1)(b+c)，这解释了为什么上述算法有效。
3. 寻找链表的中间节点
算法思想：快指针速度是慢指针的两倍，当快指针到达末尾时，慢指针正好在中间。
public ListNode findMiddle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
4. 数组去重（保留最多k次重复）
这是快慢指针在数组上的精彩应用，体现了"历史窗口"的精妙思想。
保留唯一元素（LeetCode 26）
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
保留最多两次重复（LeetCode 80）
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int slow = 2; // 前2个元素天然合法
for (int fast = 2; fast < nums.length; fast++) {
// 核心：比较当前元素与历史窗口起点元素
if (nums[fast] != nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
理解"历史窗口"：快慢指针的精髓
"历史窗口"概念是理解高级快慢指针应用的关键。让我们深入分析：
心智模型
-
可信历史：慢指针
slow维护着一个已处理的合法子数组（nums[0]到nums[slow-1]） -
历史窗口：为了判断新元素是否合法，我们需要回顾最近的相关历史，即从
slow-k开始的部分 -
决策机制：比较
nums[fast]与nums[slow-k]- 如果相等：说明新元素加入后将超过k次重复，拒绝
- 如果不相等：说明新元素安全，可以加入可信历史
通用模板
对于"保留最多k次重复"的问题，通用解决方案为：
public int removeDuplicates(int[] nums, int k) {
if (nums.length <= k) return nums.length;
int slow = k; // 前k个元素天然合法
for (int fast = k; fast < nums.length; fast++) {
if (nums[fast] != nums[slow - k]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
这种方法的巧妙之处在于，用一个单点比较替代了复杂的频率统计，将时间复杂度从O(n²)降到O(n)。
使用注意事项
- 空指针检查：在移动快指针前务必检查
fast和fast.next不为null - 初始位置：根据问题需求正确初始化指针位置
- 循环条件：仔细设计循环终止条件
- 边界情况：考虑空链表、单节点等特殊情况
总结
快慢指针技巧展现了算法设计的优雅：
- 职责分离：快指针探索，慢指针建设
- 相对运动：速度差产生解决问题的契机
- 历史窗口：通过有限的历史信息做出全局决策
- 原地操作：O(1)空间复杂度的高效解决方案
掌握快慢指针不仅意味着学会几种算法，更是培养了一种重要的算法思维模式。无论是链表操作还是数组处理，这种"一快一慢、一探一建"的思想都能为我们提供清晰的解决路径。
下次面对类似问题时，不妨思考：能否用快慢指针的不同速度差来揭示数据结构的某种规律？这种思维训练，正是算法学习的真正价值所在。