There are number of ways to solve this problem and it is really good opportunity to showcase your problem solving skills and knowledge of common data structures and algorithms. 

The most common and well known approach is based on Floyd’s cycle-finding algorithm published in the Journal of ACM (JASM), V12,  I4 in 1967. The idea is to use 2 pointers first and second initialized to the head. Then traverse the two pointers starting from the head, with first moving 1 node at a time and second moving 2 nodes at a time. If there is indeed a cycle, the nodes will meet inside the loop, otherwise they will reach the tail.

Solution 1. Floyd’s cycle-finding algorithm



public bool hasLoop(Node head) { Node first = head; Node second = head; while (first && second && first.Next && second.Next && second.Next.Next) { first = first.Next; second = second.Next.Next; if (first == second) { return true; } } return false; }

We can slightly improve this solution by letting second pointer travel at the higher speed which will significantly improve algorithm execution time for lists with large loops.



Solution 2. Floyd’s cycle-finding algorithm (modified)



public bool hasLoop(Node head) { Node first = head; Node second = head; int index = 0; int counter = 1; while (first) { first = first.Next; index++; if (first == second) {return true; } if (index == counter) { second = first; counter *= 2; } } return false; }

Solution 3. Reverse based algorithm.



If there are no requirements on using extra memory and keeping the list in its original state very neat and simple approach can be uses. The idea is based on the fact that if you reverse the list which has loops you will end-up on the head node while if list doesn’t have loops you will stop at the tail.

public bool hasLoop(Node head) { Node first=null; Node second=null; Node tmp=head; while(tmp) { first=second; second=tmp; tmp=tmp.Next; if(tmp==head) return true; second.Next=first; } return false; }






Answers and Comments