How to remove loop in LinkedList in Java ?

By | July 24, 2020

In this post, we will learn How to remove loop in LinkedList in Java. This problem statement is the extension of the below problems:

How to check whether a linked list has a loop/cycle in java ?
Find start node of the loop in Singly LinkedList in java

Circular LinkedList

After removing loop from Above image shown output should be:2 5 8 40 10 90

In order to remove a loop from LinkedList we have to follow below three steps:

  1. First, we have to check whether a loop exists in a linked list or not.

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

  • We use 2 references(slowReference & fastReference ) which are initialized to the head of the linked list.
  • slowReference hop a node and the fastReference takes two hops in each iteration.
  • If both of these references point to the same node at some iteration that means there is a loop.
  • If any of these two references pointing to null that means there is no loop in the linked list.
  1. If we find that loop exists then both pointers will meet at some node. From there we will have to find the start node of the loop.
  • First of all, we have to find a meeting point for slowReference and fastReference.
  • Next Step to set slowReference to head node of LinkedList.
  • Afterward move slowReference and fastReference both by one node at a time
  • The node at which slowReference and fastReference meets that will be starting node of the loop.
  1. Once both slowReference and fastReference are at the beginning of the loop if you move fastReference  by one node at a time ultimately it will again become equal to slowReference as it will cycle back because of the loop. That location of the fastReference  where it becomes equal to the slowReference again is the end node of the loop. To remove the loop in the LinkedList. We have to just set the next to null for the node referenced by fastReference .

Below is the complete Source code:

The output of this Program:

Loop is detected in LinkedList
Start node of the loop in Singly LinkedList is:2
After removing the loop from LinkedList:
2 5 8 40 10 90

You May Also Like:

Implementing a Circular Singly Linked List in Java ?
How to check whether a linked list has a loop/cycle in java ?
Find start node of loop in Singly LinkedList in java
Count the number of nodes in a circular linked list?
How to print circular linked list in java?

That’s all about How to remove loop in LinkedList 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.