快慢指针深度解析

快慢指针是一种常用技巧，尤其在链表和数组问题中应用广泛，我们通过使用两个速度不同的指针遍历数据结构，快慢指针能够在O(n)时间复杂度内解决许多看似需要O(n²)时间复杂度的问题。本文我将全面介绍快慢指针的基本概念、算法原理以及经典案例分析与实践。

一、基本概念

快慢指针是指在遍历数据结构（如链表、数组）时使用两个速度不同的指针。通常，快指针每次移动两步，而慢指针每次移动一步。这种速度差异使得两个指针在遍历过程中形成相对运动，从而可以解决诸如检测环、寻找中间节点、判断链表长度奇偶性等问题。

二、算法原理

快慢指针的核心思想是利用两个指针的速度差，在一次遍历中完成复杂的任务。以下是快慢指针的常见应用场景及其原理：

2.1 检测链表中的环

原理：如果链表中存在环，快指针和慢指针最终会在环内相遇。如果链表无环，快指针会先到达链表尾部。

步骤：

1. 慢指针每次移动一步，快指针每次移动两步。
2. 如果链表存在环，快指针最终会追上慢指针，即两指针相遇。
3. 如果链表无环，快指针会先到达链表尾部（null）。
   

2.2 寻找链表的中间节点

原理：当快指针到达链表尾部时，慢指针恰好位于链表中间。

步骤：

1. 慢指针每次移动一步，快指针每次移动两步。
2. 当快指针到达链表尾部（null）时，慢指针正好指向链表的中间节点。
3. 如果链表长度为偶数，中间节点为中间两个节点的前一个。

2.3 判断链表长度奇偶性

原理：遍历结束时，若快指针为null，则链表长度为偶数；若快指针不为null且快指针的下一个节点为null，则链表长度为奇数。

三、经典案例实现

3.1 链表节点定义

首先定义链表节点结构：

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}
}

3.2 检测链表中的环

public boolean hasCycle(ListNode head) {if (head == null || head.next == 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; // 快指针到达尾部，无环
}

3.3 寻找链表的中间节点

public ListNode middleNode(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow; // 慢指针指向中间节点
}

3.4 判断链表长度奇偶性

public boolean isEvenLength(ListNode head) {if (head == null) {return true; // 空链表视为偶数长度}ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next;}return fast == null; // fast为null表示偶数长度
}

四、其他应用场景

4.1 环形链表

题目描述：给定一个链表，判断链表中是否有环。

解题思路：使用快慢指针，若两指针相遇则存在环。

public class Solution {public boolean hasCycle(ListNode head) {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;}
}

4.2 环形链表II

题目描述：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

解题思路：先使用快慢指针判断是否有环，相遇后将慢指针重置到表头，两指针以相同速度移动，再次相遇点即为环的入口。

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;boolean hasCycle = false;// 检测是否有环while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {hasCycle = true;break;}}// 无环则返回nullif (!hasCycle) {return null;}// 慢指针重置到表头，两指针以相同速度移动slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow; // 相遇点即为环的入口}
}

4.3 删除链表的倒数第N个节点

题目描述：给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

解题思路：使用快慢指针，快指针先移动n步，然后快慢指针同时移动，当快指针到达尾部时，慢指针指向倒数第n+1个节点，删除其后继节点即可。

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0); // 虚拟头节点dummy.next = head;ListNode slow = dummy;ListNode fast = dummy;// 快指针先移动n步for (int i = 0; i <= n; i++) {fast = fast.next;}// 快慢指针同时移动，直到快指针到达尾部while (fast != null) {slow = slow.next;fast = fast.next;}// 删除倒数第n个节点slow.next = slow.next.next;return dummy.next;
}

复杂度分析

快慢指针算法的时间复杂度通常为O(n)，其中n为链表或数组的长度。这是因为每个指针最多遍历一次数据结构。空间复杂度为O(1)，因为只需要使用常数级的额外空间。

总结与扩展

核心思想总结

快慢指针通过两个速度不同的指针在一次遍历中完成复杂任务，避免了嵌套循环，将时间复杂度从O(n²)优化到O(n)。

扩展应用

快慢指针不仅适用于链表，还可以应用于数组和其他数据结构。例如：

• 在有序数组中寻找两个数的和等于目标值。
• 在数组中检测重复元素。
• 在环形数组中解决问题。

注意事项

• 处理链表问题时，要特别注意空指针异常和边界条件。
• 在判断链表是否有环的问题中，快指针每次移动两步是最优选择，更快的速度可能导致无法相遇。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～