Thursday, February 21, 2019

Java Program to Detect And Remove Loop in a Linked List

In this post we’ll see how to detect a loop or cycle in a linked list using a Java program and how to remove that loop in a linked list.

Linked list loop detection

If there is a loop in a linked list that means one of the node references back to any of the previous nodes rather than referencing the next node or null. Traversing 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.

Following image shows how a linked list with a loop looks like.

detecting loop in linked list

Linked list loop detection Java program

There are various options for writing a Java program for linked list loop detection.

One of the approach is to use HashSet where you add each traversed node of the linked list to the HashSet, if the same node is encountered again trying to add will return false indicating a loop. But this approach requires extra space as another data structure HashSet is used.

The implementation which is widely used for linked list loop detection is Floyd's cycle-finding algorithm also known as "tortoise and the hare" algorithm. This implementation doesn’t require auxiliary space so space complexity is O(1) and time complexity is O(n) as linear traversal of the linked list is done.

Steps for implementing this algorithm are as follows-
  1. Use 2 references which are initialized to the head of the linked list.
  2. One of them hop a node and the other 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.
public class SinglyLinkedList {
 private Node head;
 SinglyLinkedList(){
  head = null;
 }
 static class Node{
  //data
  int i;
  Node next;
  Node(int i){
   this.i = i;
   this.next = null;
  }
 }
 // Method to add nodes to linked list
 public void insertLast(Node newNode){
  if(isEmpty()){
   head = newNode;
  }else{
   Node current = head;
   // traverse to the last of the list
   while(current.next != null){
    current = current.next;
   }
   // adding new node, current last node
   // starts referencing to this new node
   current.next = newNode;
  }
 }
 public boolean isEmpty(){
  return head == null;
 }
 public boolean isLoopDetected(){
  Node fast, slow;
  // start from head 
  fast = slow = head;
  while(slow != null && fast != null && fast.next != null){
   // hops two references
   fast = fast.next.next;
   // hops one reference
   slow = slow.next;
   if(fast == slow){
    return true;
   }
  }
  return false;
 }
 
 public static void main(String[] args) {
  SinglyLinkedList list = new SinglyLinkedList();
  Node node = new Node(30);
  list.insertLast(new Node(10));
  list.insertLast(new Node(20));
  list.insertLast(node);
  list.insertLast(new Node(40));
  list.insertLast(new Node(50));
  // same node inserted again to create loop
  list.insertLast(node);
  System.out.println("Loop detected? " + list.isLoopDetected());
 }
}

Output

Loop detected? True

Removing loop in linked list

In order to remove a loop in linked list three steps are required.

  1. First is of course to check whether a loop exists in a linked list or not.
  2. If a loop exists then both pointers will meet at some node. From there you will have to find the start node of the loop. For doing that set one of the pointers to the head and the other one remains at the point where both pointers met. From there move both of them sequentially (one reference at a time). The node where both these reference meet again would be the start of the loop.
  3. Once both slow and fast pointers are at the beginning of the loop if you move fast by one reference at a time ultimately it will again become equal to slow as it will cycle back because of the loop. That location of the fast where it becomes equal to the slow again is the end node of the loop.
    To remove loop in the liked list just set the next to null for the node referenced by fast.
public class SinglyLinkedList {
 private Node head;
 SinglyLinkedList(){
  head = null;
 }
 static class Node{
  //data
  int i;
  Node next;
  Node(int i){
   this.i = i;
   this.next = null;
  }
  public void displayData(){
   System.out.println("i= " + i);
  }
 }
 // Method to add nodes to linked list
 public void insertLast(Node newNode){
  if(isEmpty()){
   head = newNode;
  }else{
   Node current = head;
   // traverse to the last of the list
   while(current.next != null){
    current = current.next;
   }
   // adding new node, current last node
   // starts referencing to this new node
   current.next = newNode;
  }
 }
 public boolean isEmpty(){
  return head == null;
 }
 
 public Node findStartOfLoop(){
  Node fast, slow;
  fast = slow = head;
  boolean loopFlag = false;
  // to check for loop
  while(slow != null && fast != null && fast.next != null){
   fast = fast.next.next;
   slow = slow.next;
   if(fast == slow){
    loopFlag = true;
    break;
   }
  }
  // Find start of the loop
  if(loopFlag){
   System.out.println("Loop detected in liked list, finding start of the loop..");
   slow = head;
   while(slow != fast){
    slow = slow.next;
    fast = fast.next;
   }
  }else{
   System.out.println("No Loop detected in the linkedlist");
   fast = null;
  }
  return fast;
 }
 
 public void removeLoop(Node startNode){
  Node fast, slow;
  fast = slow = startNode;
  
  while(fast.next != slow){
   fast = fast.next;
  }
  fast.next = null;
 }

 // Method to traverse and display all nodes
 public void displayList(){
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
 }
 public static void main(String[] args) {
  SinglyLinkedList list = new SinglyLinkedList();
  Node node = new Node(30);
  list.insertLast(new Node(10));
  list.insertLast(new Node(20));
  list.insertLast(node);
  list.insertLast(new Node(40));
  list.insertLast(new Node(50));
  // same node inserted again to create loop
  list.insertLast(node);
  
  Node loopStartNode = list.findStartOfLoop();
  System.out.println("Start node of the loop- " + loopStartNode.i);
  list.removeLoop(loopStartNode);
  list.displayList();
 }
}

Output

Loop detected in liked list, finding start of the loop..
Start node of the loop- 30
i= 10
i= 20
i= 30
i= 40
i= 50

In the code initially start node of the loop is searched and using that end node is searched. Once the end node of the loop is found its next reference is changed to null. Now the list can be traversed with going into an infinite loop.

That's all for this topic Java Program to Detect And Remove Loop in a Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Queue Implementation in Java Using Linked List
  2. How to Reverse a Doubly Linked List in Java
  3. Linear Search (Sequential Search) Java Program
  4. Heap Sort Program in Java
  5. How to Display Pyramid Patterns in Java - Part1

You may also like-

  1. Creating Tar File And GZipping Multiple Files - Java Program
  2. How to Read Properties File in Java
  3. Difference Between Two Dates in Java
  4. Find Largest and Second Largest Number in Given Array - Java Program
  5. How HashMap Internally Works in Java
  6. Generics in Java
  7. Conditional Operators in Java
  8. Spring Web MVC Tutorial