当前位置：首页 > news >正文

快慢指针算法（Floyd 判圈算法）

news 2025/5/17 5:31:43

快慢指针（又称龟兔赛跑算法）是一种常用的链表操作技巧，通过两个移动速度不同的指针遍历链表，用于解决链表中环检测、中点查找等问题。以下是其核心应用场景和实现方法：

1. 链表环检测

问题描述： 判断链表中是否存在环。
算法思路：
- 慢指针（slow）每次移动 1 步。
- 快指针（fast）每次移动 2 步。
- 若存在环，快指针会追上慢指针（即相遇，slow == fast）。
- 若无环，快指针会先到达链表尾部（null）。

代码实现：

function hasCycle(head) {if (!head) return false;let slow = head;let fast = head.next;while (slow !== fast) {if (!fast || !fast.next) return false;slow = slow.next;fast = fast.next.next;}return true;
}

复杂度分析：
- 时间复杂度： O (n)，快指针最多遍历 2n 步。
- 空间复杂度： O (1)，仅需两个指针。

2. 寻找链表中点

问题描述： 找到链表的中间节点（若节点数为偶数，返回中间两个节点的任意一个）。
算法思路：
- 慢指针每次移动 1 步。
- 快指针每次移动 2 步。
- 当快指针到达尾部时，慢指针恰好位于中点。

代码实现：

function middleNode(head) {let slow = head;let fast = head;while (fast && fast.next) {slow = slow.next;fast = fast.next.next;}return slow;
}

3. 寻找环的入口节点

问题描述：若链表存在环，找到环的入口节点。
算法思路：
- 步骤 1： 使用快慢指针判断是否存在环，并找到相遇点。
- 步骤 2： 相遇后，将慢指针重新指向头节点，快指针保持在相遇点。
- 步骤 3： 慢指针和快指针同时移动 1 步，再次相遇的位置即为环的入口。

代码实现：

function detectCycle(head) {if (!head) return null;let slow = head;let fast = head;// 找到相遇点while (fast && fast.next) {slow = slow.next;fast = fast.next.next;if (slow === fast) break;}// 若无环，返回nullif (!fast || !fast.next) return null;// 慢指针回到头节点，再次相遇即为入口slow = head;while (slow !== fast) {slow = slow.next;fast = fast.next;}return slow;
}

4. 链表倒数第 k 个节点

问题描述： 找到链表的倒数第 k 个节点。
算法思路：
- 快指针先移动 k 步。
- 慢指针和快指针同时移动 1 步，直到快指针到达尾部。
- 此时慢指针即为倒数第 k 个节点。

代码实现：

function findKthFromEnd(head, k) {let slow = head;let fast = head;// 快指针先走k步for (let i = 0; i < k; i++) {if (!fast) return null;fast = fast.next;}// 同步移动至快指针到达尾部while (fast) {slow = slow.next;fast = fast.next;}return slow;
}