單鏈表環檢測與入口節點定位：演算法深度解析

編輯：關於C語言

前言

在資料結構與演算法面試中，「判斷單鏈表是否有環」與「找到環的入口節點」是經典必考題目。本文將系統梳理三種主流解法：雙指針法（Floyd 判圈演算法）、哈希集合法與暴力雙重循環法，並附上 C++ 完整實現碼，幫助你徹底掌握核心邏輯與時間空間複雜度權衡。

一、問題定義

給定單鏈表頭指針 head，判斷鏈表中是否存在環。若存在，返回環的入口節點（即第一個進入環的節點）；否則返回 NULL。

單鏈表環結構示意圖

二、演算法對比

1. 暴力雙重循環法 —— `findFirstCycleNode`

思路：外層指針 pCur 遍歷每個節點，內層指針 pStart 從頭開始尋找是否能遇到 pCur。若 pStart 走到 pCur 時步數相等，說明 pCur 不在環中；若步數不等，則 pStart 為入口節點。

時間複雜度：O(n²)
空間複雜度：O(1)
缺點：效率極低，僅適合教學演示。

2. 哈希集合法 —— `findFirstCycleNode2`

思路：遍歷鏈表，將訪問過的節點地址存入 std::set<Linknode*>。若發現當前節點已在集合中，即為入口節點。

時間複雜度：O(n)
空間複雜度：O(n)
優點：代碼簡潔，易於理解與除錯。

3. 快慢指針法（Floyd 判圈演算法） —— 推薦方案

思路：

快指針 fast 每次走兩步，慢指針 slow 每次走一步。若相遇，證明有環。
將其中一指針重置為 head，兩指針改為同速（每次一步）前進，再次相遇處即為入口節點。

數學證明：設頭節點到入口距離為 a，入口到相遇點距離為 b，環長為 L。相遇時 slow 走 a+b，fast 走 2(a+b)，差值 a+b = kL ⇒ a = kL - b。因此從頭出發與從相遇點出發同速走 a 步必在入口相遇。

時間複雜度：O(n)
空間複雜度：O(1)
優點：最優空間，面試首選。

三、C++ 核心代碼實現

3.1 節點定義與建環測試工具

struct Linknode {
    int data;
    Linknode* next;
    Linknode(int val) : data(val), next(nullptr) {}
};

// 建立帶環鏈表：最後一個節點指向 head->next（即第 2 個節點）
Linknode* createCycleList(int n) {
    if (n <= 1) return nullptr;
    Linknode* head = new Linknode(1);
    Linknode* cur = head;
    for (int i = 2; i <= n; ++i) {
        cur->next = new Linknode(i);
        cur = cur->next;
    }
    cur->next = head->next; // 形成環，入口為第 2 個節點
    return head;
}

3.2 快慢指針法標準實現

Linknode* detectCycleEntry(Linknode* head) {
    if (!head || !head->next) return nullptr;

    Linknode *slow = head, *fast = head;
    // 階段 1：判斷是否有環
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break; // 相遇
    }
    if (!fast || !fast->next) return nullptr; // 無環

    // 階段 2：定位入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // 入口節點
}

3.3 哈希集合法實現（參考）

#include <unordered_set>
Linknode* detectCycleEntryHash(Linknode* head) {
    std::unordered_set<Linknode*> visited;
    while (head) {
        if (visited.count(head)) return head;
        visited.insert(head);
        head = head->next;
    }
    return nullptr;
}

四、測試驗證

int main() {
    Linknode* head = createCycleList(10); // 10 節點，入口為節點 2
    Linknode* entry = detectCycleEntry(head);
    if (entry) 
        std::cout << "環入口節點值：" << entry->data << std::endl; // 輸出 2
    else
        std::cout << "無環" << std::endl;
    return 0;
}