Detecting Cycles in Linked Lists

mgcadmin 11-01-2022

Detecting a Cycle in a Linked Lists

I was asked for a solution to this question on quora in the C programming section, and since i put a detailed answer there, i figured i would post my solutions here as well to reach a broader audience.

Linked lists are *supposed* to be a sequential data structure, being a recursively defined data structure they have the ability to form cycles, either purposely (in a circular list for example) or by mistake(the purpose of this article). Because an inadvertent cycle being introduced to a linked list has the potential to cause traversal based algorithms, such as searching the list to devolve into an infinite loop, being able to detect cycles is important.

In this article i will discuss two (2) approaches to detecting cycles. One algorithm based on disjoint sets requiring O(n) extra space, and one algorithm based on the fast/slow pointer traversal method which requires O(1) constant space.

Detecting Cycles using Sets

This is a very simple technique running O(n * nlogn). You traverse through the list checking each node against the set, if the set does not contain the node, add it to the set. If the node IS already in the set, you have a cycle! easy peasy, and it is a good demonstration for the use of sets in regards to membership tests.

 

Detecting Cycle via fast/slow pointer traversal

This is a pretty slick method for detecting cycles. It uses the same technique employed for finding the halfway point in a linked list for mergesort. In this case however, if the list is cyclic it will detect the cycle instead of ending.

Client Code for examples

---