快慢指針（又稱龜兔賽跑算法）是一種常用的鏈表操作技巧，通過兩個移動速度不同的指針遍歷鏈表，用于解決鏈表中環檢測、中點查找等問題。以下是其核心應用場景和實現方法：

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)，是鏈表操作中的經典技巧。