Finding a loop in a linked list

Problem

We are given a singly linked list and we need to tell whether it is a null terminated Linked List or a cyclic (having a loop) Linked List.

 

Solution

Take two pointers, fast (hops 2 nodes at a time) & slow (hops a single node in a jump).
Keep moving these pointers till, either fast becomes null or fast catches up slow.

If fast becomes null, it means that the Linked List is null terminated and its catching up with slow indicates the loop in the linked list.

 

Step 1:

 

Step 2:

 

 

Step 3:

Step 4:

 

Step 5:

 

Step 6:

Step 7:

 

 

Source Code

Copy the code in SinglyLinkedList.java or SinglyCircularLinkedList.java file from the previous tutorials to quickly test the method if you want or you can use it in your own code somewhere in your project.