快慢指针算法/龟兔算法/Floyd's cycle-find algorithm

算法描述

有两个指针，一个跑的快，一个跑得慢。在龟兔赛跑的寓言中，跑的快的称为 “乌龟”，跑得快的称为 “兔子”。不管乌龟和兔子在循环中从哪里开始，它们最终都会相遇。这是因为兔子每走一步就向乌龟靠近一个节点（在它们的移动方向上）。

通过快慢指针则可以避免使用数据结构记忆，检测是否有循环，在求取最短路径也会使用。

算法模版

代码中使用的是链表结构

while (fastNode && fastNode.next()) {
    if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
        return true;
    }
    fastNode = fastNode.next().next();
    slowNode = slowNode.next();
}

参考链接

弗洛伊德循环查找算法(快慢指针法/龟兔指针法)

ps: 这一点也可以通过玩轮滑验证，你和朋友去公园玩轮滑，环形滑道，一个滑的快，一个滑的慢，两人最终会相遇。