Do you know any better than than Floyd’s algorithm for cycle detection?

Technology CommunityCategory: Linked ListsDo you know any better than than Floyd’s algorithm for cycle detection?
VietMX Staff asked 1 year ago

Richard Brent described an alternative cycle detection algorithm, which is pretty much like the hare and the tortoise Floyd’s cycle except that, the slow node here doesn’t move, but is later “teleported” to the position of the fast node at fixed intervals.

Brent claims that his algorithm is 24% to 36% faster than the Floyd’s cycle algorithm.

Complexity Analysis
Implementation
public static boolean hasLoop(Node root) {
    if (root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if (slow == fast) return true;

        if (taken == limit) {
            taken = 0;
            limit <<= 1; // equivalent to limit *= 2;
            slow = fast; // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}