Floyd's cycle-finding algorithm(Tortoise & Hare)

Floyd's cycle-finding algorithm :-

• The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes. If the linked list has a loop they will definitely meet.
• Else either of the two references(or their next) will become null.

below are the total ways we can use to detect the cycle ..

Method 1( Hash Table ) :- Traverse the Linked List and store the node pointers in a hash table. As soon as you discover a collision, you’ve discovered a loop!

Method 2( List Reversal):- Traverse the Linked List and start reversing it. If there is a loop, you shall revisit the head again. However, the “loop” in the list has been reversed — to fix that, traverse the list again, reversing the pointers!

Method 3( Mark Visited Node ):- Traverse the Linked List and keep marking the node as visited. if you re-visit same node means there is a loop in the given Linked List.

Method 4(Floyd’s Cycle-Finding Algorithm or Two Pointers Algorithm) :- Traverse the Linked List using two pointers. slower pointer moves one step while faster pointer moves forward two steps. If these pointers meet at some node, then there is a loop.