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;
};

参考资料