VietMX Staff asked 3 years 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;
}