How to Detect a Cycle in a Linked List (Floyd's Algorithm)

A cycle in a linked list means that at some point, a node's next pointer points back to a previous node instead of NULL. If you traverse such a list normally, you will never reach NULL and your program will run forever.

Create two pointers. Set both SLOW and FAST to HEAD. SLOW will move one step at a time and FAST will move two steps at a time.

Inside a loop, move SLOW to SLOW.next and move FAST to FAST.next.next in every single iteration.

After moving both pointers, check if SLOW and FAST are pointing to the same node. If they are equal, a cycle has been detected. Return true and stop.

Before moving FAST two steps forward, always verify that FAST is not NULL and FAST.next is not NULL. If either is NULL, the list has a proper end and there is no cycle. Return false.

Keep repeating the movement and both checks inside the loop. Either the two pointers will meet confirming a cycle, or FAST will fall off the end confirming there is no cycle.

Think of two runners on a circular track. The faster runner will always eventually lap the slower one. If the list is circular, FAST keeps gaining on SLOW by one step each iteration and they will inevitably land on the same node.