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

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

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;
  }
  

总结

• 快慢指针算法通过速度差，巧妙地解决了链表中的多种问题。其核心在于：

  • 环检测：快慢指针相遇则有环。
  • 中点查找：快指针到尾时慢指针在中点。
  • 环入口定位：相遇点和头节点同时移动再次相遇处。
  • 倒数第 k 个节点：快指针先走 k 步后同步移动。

该算法时间复杂度均为 O (n)，空间复杂度为 O (1)，是链表操作中的经典技巧。