快慢指针算法（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;
      }
      
      // 若无环，返回null
      if (!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)，是链表操作中的经典技巧。