單向鏈表環檢測與入口定位：Floyd 判圈演算法完整解析

單向鏈表若存在環（某節點 next 指向前序節點），普通遍歷會陷入無限迴圈。本文詳細解析 **Floyd 判圈演算法（快慢指針）** 的數學原理、代碼實作、環入口定位邏輯，並延伸至無環雙鏈表相交判斷。

一、判斷是否存在環：快慢指針

bool has_cycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;       // 1 步
        fast = fast->next->next; // 2 步
        if (slow == fast) return true; // 相遇 → 有環
    }
    return false; // fast 到達 NULL → 無環
}

數學證明：為什麼必相遇？

• 設環長 L，慢指針進環時快指針已在環內領先 k 步
• 相對速度 1 步/輪，最多 L 輪追上
• 若無環，fast 先到達 NULL 終止

二、尋找環入口：雙指針二次相遇

ListNode* find_cycle_entry(ListNode* head) {
    ListNode *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，雙指針同速前進
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // 相遇點即環入口
}

數學推導

設：

• a：頭節點到環入口距離
• b：環入口到相遇點距離
• L：環長

相遇時：slow 走 a+b，fast 走 a+b+nL (n≥1)

因 fast = 2 × slow → a+b+nL = 2(a+b) → a = nL - b = (n-1)L + (L-b)

L-b 即相遇點到入口距離。故從頭出發走 a 步，與從相遇點出發走 a 步，必在入口相遇。

三、延伸：無環雙鏈表相交判斷

方法 1：構造環法（破壞原結構，需恢復）

1. 將鏈表 A 尾接頭，形成環
2. 在鏈表 B 上跑判圈 → 有環則相交，入口即交點
3. 恢復鏈表 A 尾部 next = NULL

方法 2：長度差對齊法（非破壞、O(1) 空間）

ListNode* get_intersection(ListNode* headA, ListNode* headB) {
    // 1. 遍歷得長度與尾節點
    int lenA=0, lenB=0;
    ListNode *pA=headA, *pB=headB, *tailA=NULL, *tailB=NULL;
    while (pA) { ++lenA; tailA=pA; pA=pA->next; }
    while (pB) { ++lenB; tailB=pB; pB=pB->next; }
    if (tailA != tailB) return NULL; // 尾不同 → 不相交

    // 2. 長鏈表先走差值步
    pA = headA; pB = headB;
    if (lenA > lenB) for (int i=0; inext;
    else for (int i=0; inext;

    // 3. 同步前進直到相遇
    while (pA != pB) { pA = pA->next; pB = pB->next; }
    return pA;
}

四、複雜度總結

Floyd 演算法以極簡代碼解決看似需要額外空間的問題，是指標演算法中的經典典範。理解其數學本質，有助於舉一反三解決更多鏈表、圖論中的週期檢測問題。