題目網址：https://leetcode.cn/problems/linked-list-cycle-ii/

題意：給一 linked list 的 head, 返回 cycle 的起點。若無 cycle, 則返回 null。

進階：設計 $O(1)$ space 的演算法

Solution：

想法：定義以下變數

  • L 是起始點和 cycle head 的距離
  • x 是 cycle head 到第一次相遇的距離
  • C 是整個 cycle 的長度

第一次相遇可以寫成一個等式：2(L + x) = L + nC + x
其中, L + x 為烏龜走的步數, L + nC + x 為兔子走的步數
nC 代表兔子率先進入 cycle, 在和烏龜第一次相遇之前可能已經繞 cycle 好幾圈了

2(L + x) = L + nC + x 可化簡成 L + x = nC

  • 讓烏龜回到原點, 然後走 L 步抵達 cycle head

  • 兔子則在第一次相遇的地方 (L+x) 走 L 步
    此時兔子的新位置在 (L + x) + L = nC + L 也就是在 cycle head
    (nC + L 可看成從起點走 L 步到達 cycle head, 然後繞了 cycle n 圈, 位置仍在 cycle head)

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                slow = head;
                while (fast != slow) {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;
            }
        }

        return nullptr;
    }
};
  • time：$O(n)$ ➔ cycle 長度不超過 n
  • space：$O(1)$ ➔ 只需常數空間