Brent's Algorithm
Brent's Cycle detection Algorithm Given a linked list, check if the linked list has loop or not. Below diagram shows a linked list with a loop. Brent’s cycle detection algorithm is analogous to Floyd's algorithm because it also uses two pointer technique. But there's some difference in their approaches. Here we make one pointer stationary till every iteration and teleport it to other pointer at every power of two. the beginning of the cycle is decided by the littlest power of two at which they meet. This improves upon the constant factor of Floyd’s algorithm by reducing the amount of calls. Move fast pointer (or second_pointer) in powers of two until we discover a loop. After every power, we reset slow pointer (or first_pointer) to previous value of second pointer. Reset length to 0 after every every power. The condition for loop testing is first_pointer and second_pointer become same. And loop isn't present if second_pointer becomes NULL. The condition for loop test...