目錄

初始思考：什么叫“鏈表有環”？

? 第一種直接想法（失敗）：我們是不是能“記住走過的節點”？

那我們換一個思路：我們能否只用兩個指針來檢測環？

第一步：定義兩個指針

第二步：建立循環

---

初始思考：什么叫“鏈表有環”？

鏈表的本質是：

Node → Node → Node → NULL

但如果鏈表中某個節點的 next 指針不是 NULL，而是指向之前的某個節點：

Node → Node → Node  ↑         ↓  ←←←←←←←←←←

這就變成了一個“環形結構”。

?我們怎么知道某個鏈表有沒有環？

你無法一次看完所有節點。你只能從頭開始，一個一個往后走：

while (p != NULL) {p = p->next;
}

正常情況下你最終會走到 p == NULL

但是如果鏈表有環，你會一直繞圈，永遠也走不到 NULL，程序變成死循環。

---

? 第一種直接想法（失敗）：我們是不是能“記住走過的節點”？

想法：

每訪問一個節點，就記住它；
如果某個節點我們第二次看到，就說明有環。

這個思路需要什么？
需要能“記住所有走過的節點”，并判斷是否“已經訪問過”

?? 但我們沒有 STL、沒有哈希表、沒有額外空間！

所以這個方法不符合第一性原則的最低資源要求，我們暫時排除。

---

那我們換一個思路：我們能否只用兩個指針來檢測環？

想象一下：

如果你在一個環形跑道上，有兩個人：

• 一個人慢跑（每次走一步）

• 一個人快跑（每次走兩步）

如果跑道沒有環，快跑的人會直接跑出終點。

如果跑道是環形的，快跑的人遲早會“追上”慢跑的人！

這就是 Floyd’s Cycle Detection Algorithm（龜兔賽跑法）

我們現在從零構建它！

---

第一步：定義兩個指針

slow = head;
fast = head;

• slow 每次走一步：slow = slow->next

• fast 每次走兩步：fast = fast->next->next

?這一步是算法核心，“快指針”在追“慢指針”?

第二步：建立循環

變量	含義
slow	模擬“正常訪問”的一步步訪問
fast	模擬“追趕檢測”的兩步步訪問
slow==fast	表示 fast 追上 slow，說明有環
fast==NULL	表示鏈表已經結束，無環

問題：我們什么時候會出錯？

• 如果 fast == NULL：說明走到尾部

• 如果 fast->next == NULL：再走一步就越界

我們必須確保兩個指針不越界（避免訪問 NULL 的 next）：

while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;if (slow == fast) {// 二者相遇，說明有環}
}

?為什么 slow 和 fast 相遇就說明有環？

因為只有在環中，快指針才有可能“繞回來追上慢指針”

就像操場上，跑得快的人終將追上慢跑的那個人。

如果沒有環，fast 最終會變成 NULL 或 fast->next == NULL，循環終止。

如果鏈表中有環，兩個指針最終會在環中某處相遇：

if (slow == fast)return 1;  // 有環

空鏈表或一個節點鏈表怎么辦？

• 如果 head == NULL：直接退出循環，返回 0 ?

• 如果只有一個節點：fast->next == NULL，也會直接退出 ?

?完整代碼

int hasLoop(struct Node* head) {struct Node* slow = head;struct Node* fast = head;// Step 1: 同時從頭開始，每次走一步和兩步while (fast != NULL && fast->next != NULL) {slow = slow->next;             // 慢指針走一步fast = fast->next->next;       // 快指針走兩步if (slow == fast)              // 相遇 → 有環return 1;}// Step 2: 如果快指針走到了鏈表尾部，說明無環return 0;
}

時間 & 空間復雜度分析

復雜度	說明
時間復雜度	O(n)，最壞情況 fast 會走到鏈表盡頭（或追上 slow）
空間復雜度	O(1)，只用了兩個指針變量，無需額外空間

我們從“什么都不會”出發，只知道我們：

• 只能走 ->next

• 不允許記錄歷史

• 想辦法“檢測重復訪問”

最終我們想到“相遇 → 有環”的思路，從而構建出用兩個指針的檢測算法。