Cycles in a Linked List

Provide an algorithm that will detect a cycle in a given Linked List

Example of a cycle within a linked list

Simple Solution

There are a variety of cycle-finding algorithms out there, but the one being discussed will be Floyd’s Cycle-Finding Algorithm. This algorithm traverses the linked list using two pointers, one called the fast pointer that increments by two nodes and another pointer called the slow pointer that increments by one node. If these nodes meet at the same node, there is a loop, and if not, the linked list does not contain a cycle.

In-Depth Solution

• Initialize the slow and fast pointer to the head of the linked list.
• Iterate while both pointers are not null and fast_pointer->next is not null
• Inside the while loop, increment the slow pointer by 1, and the fast pointer by two.
• After the increments, if the slow pointer is equal to the fast pointer, return true.
• If you reach the end of the while loop without the slow pointer being equivalent to the fast pointer, then you know there is not a cycle so return false.

Implementation

Further Reading

Detect loop in a linked list - GeeksforGeeks

Detect cycle in a linked list (Floyd's Cycle Detection Algorithm)