142. 環形鏈表 II

思路

假設快指針$fast$每次走兩步，慢指針$slow$每次走一步，如果鏈表當中有環。
最後快指針一定會追上慢指針。 定義以下變數

• $L_1$：從頭節點$\to$環起點的距離
• $L_2$：從環起點$\to$相遇點的距離。
• $C$：環的長度。 因為快指針的速度是慢指針的兩倍，所以$2(L_1+L_2)=L_1+L_2+nC$，其中$n$代表快指針追過了幾圈慢指針。（因為快指針可能直接越過慢指針）\
• 經過化簡得到：$L_1+L_2=nC \to L_1=nC-L_2$，
• 取出一個$C$跟$L_2$組合：$L_1=(n-1)C+(C-L_2)$ 也就是說，一開始放入$A,B$兩指針，速度分別為 1, 2，會在距離環起點$L_2$的位置相會，
  這時將$A$放到起點，走過$L_1$的距離，此時$B$在裡面走了$(n-1)C+(C-L_2)$的距離，而它一開始在交會點$L_2$，
  因此現在的位置在$L_2 + (n-1)C+(C-L_2) = nC$，也就是環的起點。

程式碼

快慢指針

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr) {
            return nullptr;
        }
        
        // 初始化指針
        ListNode *slow = head->next, *fast = head->next->next;
        while(slow != fast) {
            if(fast->next == nullptr || fast->next->next == nullptr) {
                // 走到終點，沒有環
                return nullptr;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        // 重回起點，找到交會點 (必定是環的起點)
        slow = head;
        while(slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$