Find the start point of a Loop in a Singly LinkedList if there is any Loop?

In this article we are going to find the node in a singly LinkedList, where a Loop starts , if there is a loop exists in the LinkedList. The solution is a extension to the problem of finding the existence of a Loop in a linked list. Finding the loop in a linked list was solved using Floyd cycle detection algorithm in this article. It is highly recommended to read the cycle finding solution before continuing in this solution. Consider the following figure of a singly linked list with a loop where the starting position of the loop is the third node with value 3.

 

After finding the loop in the linked list, we initialize the slowPtr to the head of the linked list. From that point onwards both slowPtr and fastPtr move only one node at a time. The point at which they meet is the start of the loop. Generally we use this method for removing the loop. Following is the linked list ADT we are using for solving the problem.

Node.java

package com.algo.linkedlist;

public class Node {

 int data;
 Node next;

 public Node(int data) {
  this.data = data;
  this.next = null;
 }

 @Override
 public boolean equals(Object o) {
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  Node node = (Node) o;
  return data == node.data && next == node.next;
 }

 public void print() {
  System.out.print(this.data);
 }
}

Following is the LinkedList class. Where the second Constructor is used to create a linked list of specified size with a loop. The loop will be created in node specified by loopStartAt position.        

package com.algo.linkedlist;

/**
 * Created by ardas on 9/14/2018.
 */
public class LinkedList {

 Node head;

 /**
  * Create a Singly LinkedList of given size
  *
  * @param size Size of the LinkedList
  */

 public LinkedList(int size) {
  head = new Node(1);
  Node tempNode = head;
  for (int i = 2; i <= size; i++) {
   Node node = new Node(i);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
 }

 /**
  * Create a LinkedList with a Loop
  *
  * @param size  Size of the LinkedList
  * @param loopStartAt where the Loop Start
  */
 public LinkedList(int size, int loopStartAt) {
  head = new Node(1);
  Node tempNode = head;
  for (int i = 2; i <= size; i++) {
   Node node = new Node(i);
   tempNode.next = node;
   tempNode = tempNode.next;
  }
  Node loop = head;
  for (int i = 1; i < loopStartAt; i++) {
   loop = loop.next;
  }
  tempNode.next = loop;
 }
}

Following method will returns the Node, which is the starting position of the loop, or returns NULL if there is no loop present in the singly linked list.

public Node loopStartsAt(Node head) {
 boolean hasLoop = false;
 Node fastPtr = head;
 Node slowPtr = head;
 while (fastPtr != null && fastPtr.next != null) {
  fastPtr = fastPtr.next.next;
  slowPtr = slowPtr.next;
  if (fastPtr != null && fastPtr.equals(slowPtr)) {
   hasLoop = true;
   break;
  }
 }
 slowPtr = head;
 Node loopStartAt = null;
 if (hasLoop) {
  while (true) {
   slowPtr = slowPtr.next;
   fastPtr = fastPtr.next;
   if (slowPtr.equals(fastPtr)) {
    loopStartAt = slowPtr;
    break;
   }
  }
 }
 return loopStartAt;
}

Now the method can be tested by the following pieces of code

// LinkedList where the loop starts at position 3
LinkedList linkedListWithLoop = new LinkedList(10, 3);

// get the node where the loop starts
Node startPosition = loopStartsAt(linkedListWithLoop.head);

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself