Floyd's Cycle Detection

Floyd’s Cycle Detection
Categories:
Tags:

使用情境

  • 當有節點發生迴圈的狀況，可以用 Floyd's Cycle Detection 檢測迴圈的點在哪
  • 產生 2 個指針 指向同一個起點，一個指針為 slowPointer 慢指針、一個指針為 fastPointer 快指針
  • fastPointer 快指針 移動的速度是 slowPointer 慢指針 的 2 倍速
  • 如果 2 個指針，移動到最後的節點，沒有相遇，表示此串列沒有 迴圈 cycle
  • 如果 2 個指針，移動到某個節點相遇了，表示 fastPointer 快指針 從後面追上了 slowPointer 慢指針，那表示這個串列 有迴圈 cycle

判斷發生迴圈的點在哪

  • 當 2 個指針第一次相遇後，將其中一個指針設定為之前的起點，假設為指針 resetPointer，其中一個指針留在原本的迴圈中，假設叫做指針 cyclePointer
  • 然後 2 個指針都變回 慢指針，都一次只移動 1 步
  • 當兩個指針再次相遇，那個點就是導致 迴圈 cycle 的點
  • 而在導致 迴圈 cycle 的點，維持原本 resetPointer 不動，cyclePointer 自行移動，最後再次與 resetPointer 相遇，那移動的步數，就是整個迴圈的長度

程式

TypeScript

function findDuplicate(numsList: number[]): number {
    // Floyd's Cycle Detection
    // 慢指針
    let slowPointer = 0;
    // 快指針，移動速度是「慢指針」的 2 倍
    let fastPointer = 0;

    while (true) {
        // 移動慢指針
        slowPointer = numsList[slowPointer];
        // 移動快指針
        fastPointer = numsList[numsList[fastPointer]];
        if (slowPointer == fastPointer) {
            // 「慢指針」與「快指針」相遇
            break;
        }
    }

    // 重設新的指針，與在迴圈中的慢指針比較
    let slowPointer2 = 0;
    while (true) {
        // 移動兩指針用同樣的速度
        slowPointer = numsList[slowPointer];
        slowPointer2 = numsList[slowPointer2];
        if (slowPointer == slowPointer2) {
            // 兩指針相遇，相遇的點就是迴圈發生的點
            break;
        }
    }

    // 迴圈發生的點就是重複的數字
    return slowPointer;
};

參考資料