TORTOISE AND HARE ALGORITHM(Floyd's Cycle Finding Algorithm)

Floyd's Cycle Finding Algorithm

Floyd's cycle finding algorithm is also know as TORTOISE AND HARE ALGORITHM.It is used for two different purposes in data structures.

• To Find Cycles in graphs.
• To Find Cycles in  linked list.

Algorithm:

I like to explain the algorithm by means of a singly linked list.We construct a singly linked list with one data member and an address location.The algorithm consist of two pointer,we take them as X and Y

• LET X BE TORTOISE 
• LET Y BE HARE

AT STARTING:

•  LET X BE IN FIRST POSITION 
• AND Y BE IN Kth POSITION(lets take k as 3rd position).

TRAVERSAL OF  HARE AND TORTOISE

• Increment the Tortoise position by ONE.(X+1)
• Increment the Hare position by TWO(Y+2)

IN CASE OF A CYCLE

• THE TORTOISE AND HARE WILL MEET.

• OR WHEN THE HARE OVER TAKES THE TORTOISE.

IN CASE IF THERE IS NO CYCLE

• THE HARE WILL REACH THE END OF THE LINKED LIST.

DISADVANTAGE

• It has a time complexity of O(length of loop to be find+first node of equal value).