單鏈表環檢測：兩種經典算法的 C 語言實現與對比

單鏈表環檢測：兩種經典算法的 C 語言實現與對比

判斷單鏈表是否存在環是面試與工程中的高頻問題。本文實現並對比兩種算法：步長差值法 與 快慢指針法（Floyd 判圈算法）。

數據結構與測試用例構建

typedef struct Node { int data; struct Node* next; } Node, *LinkList;

// 無環鏈表：尾結點 next = NULL
void CreateSimpleCycleList_withoutLoop(LinkList* L, int number) { ... }

// 有環鏈表：尾結點 next 指向第 loopInIndex 個結點（0 為頭結點）
void CreateSimpleCycleList_withLoop(LinkList* L, int number, int loopInIndex) { ... }

算法一：步長差值法

原理：外層指針 p 從頭遍歷，內層指針 q 每次從頭走到 p。若無環，q 走過的步數 step_i 恆等於外層步數 step_o；若有環，p 進入環後繼續走，q 仍從頭走，兩者步數差將暴露環的存在。

void JodgeLoop(LinkList L) {
    LinkList p = L, q = L;
    int step_o = 0, step_i = 0, isLoop = 0;
    while (p) {
        step_i = 0; q = L;
        while (q != p) { q = q->next; step_i++; }
        if (step_o != step_i) { isLoop = 1; break; }
        p = p->next; step_o++;
    }
    if (isLoop) printf("存在環，入環位置索引 %d\n", step_i);
    else printf("無環\n");
}

複雜度：時間 O(n²)，空間 O(1)。理解直觀但效率較低。

算法二：快慢指針法（推薦）

原理：快指針 quick 每次走兩步，慢指針 slow 每次走一步。若有環，快指針終將在環內追上慢指針（相對速度 1 步/輪）；若無環，快指針先到達 NULL。

void JodgeLoop_2(LinkList L) {
    LinkList quick = L, slow = L;
    int isLoop = 0;
    while (quick && quick->next) {
        quick = quick->next->next;
        slow = slow->next;
        if (quick == slow) { isLoop = 1; break; }
    }
    if (isLoop) printf("存在環\n");
    else printf("無環\n");
}

複雜度：時間 O(n)，空間 O(1)。業界標準解法，亦可延伸求環入口、環長度。

測試結果對比

對 5 節點有環鏈表（環入口索引 1）與 4 節點無環鏈表：

• JodgeLoop：正確識別有環並給出入口位置；無環正確判斷。
• JodgeLoop_2：同樣正確，但執行速度顯著更快。

總結

快慢指針法以優雅的數學洞察實現了最優複雜度，是鏈表環檢測的首選。掌握其「相遇必在環內、入口查找對稱性」的進階推導，能解決更多變體問題（如 LeetCode 142 環形鏈表 II）。