單鏈表環檢測與入口點定位：Floyd 判圈算法深度解析與延伸應用

問題背景：單鏈表中的環

單鏈表中若某節點的 next 指標指向了它之前的某個節點，便形成了環。這在資料結構錯誤、記憶體破壞或特定演算法需求中都可能出現。核心問題有二：

1. 如何判斷鏈表是否存在環？
2. 若存在環，如何找到環的入口節點？

經典解法：快慢指標（Floyd 判圈算法）

設置兩個指標 slow 與 fast，初始均指向頭節點。slow 每次前進一步，fast 每次前進兩步。若鏈表有環，fast 必定先進入環，slow 後進入，兩者在環內必然相遇。若 fast 先到達 NULL，則無環。

bool HasLoop(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    return !(fast == NULL || fast->next == NULL);
}

尋找環的入口點：數學推導與程式碼實現

當 fast 與 slow 相遇時，設 slow 走了 s 步，fast 走了 2s 步。環長為 r，fast 在環內多轉了 n 圈（n ≥ 1），則 2s = s + n·r ⇒ s = n·r。

設鏈表總長 L，入口到相遇點距離 x，頭到入口距離 a。則 a + x = n·r。移項得 a = (n-1)·r + (r - x)。其中 (r - x) 正是相遇點到入口點的距離。因此，從頭節點與相遇點同時出發、每次各走一步，兩指標必定在入口點首次相遇。

Node* FindLoopEntrance(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return NULL; // 無環

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // 入口點
}

延伸應用：判斷兩個無環單鏈表是否相交

若兩無環鏈表相交，從相交點到尾部節點完全相同。方法一：將一鏈表首尾相連，檢測另一鏈表是否有環（轉化為環檢測問題）。方法二：分別遍歷得長度 L1、L2，長鏈表先走 |L1-L2| 步，再同步前進，首次相遇點即為相交點。

掌握 Floyd 算法及其數學原理，不僅能解決環檢測與入口定位，更能舉一反三處理鏈表相交、環長計算等進階問題，是演算法面試與系統開發的必備利器。