How to check whether a linked list has a loop/cycle in java ?

By | June 16, 2020

In this post, We will write a java program to check whether a linked list has a loop/cycle in java?

If there is a loop in a linked list that means one of the node refers back to any of the previous nodes rather than referencing the next node to null. If we traverse a linked list with loop will cycle back to the old node rather than concluding its traversal once null is reached causing an infinite loop.

Steps for checking whether LinkedList has loop or cycle is not are as follows-

  1. We use 2 references(slowReference & fastReference ) which are initialized to the head of the linked list.
  2. slowReference hop a node and the fastReference takes two hops in each iteration.
  3. If both of these references point to the same node at some iteration that means there is a loop.
  4. If any of these references reach null that means there is no loop in the linked list.

Output of above Program:

true

This output shows the Linked list has a loop or cycle.

NOTE:After uncommenting  //linkedList.displayLinkedList();  if you run above program then you will get output as below:

10->20->30->40->50->60->70->40->50->60->70->40->50->60->70->40->50->60->70->40->50->60->70->40->50…………………………………..

This output shows that Linked List has a loop or Cycle.

Another approach:

we can take a HashSet where we add each traversed node of the linked list to the HashSet, if the same node is encountered again while adding then we will return true indicating a loop or cycle. But this approach requires extra space as another data structure HashSet is used.

You May Also Like:

Java program to add two matrices
Java program to find maximum element in each row of the matrix
Java program to find maximum and minimum numbers in the given matrix

That’s all about How to check whether a linked list has a loop/cycle in java ?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published. Required fields are marked *