We have a singly-linked list and want to check if it contains a cycle

The difference between a regular LinkedList and a LinkedList with a Loop is that, There are two nodes in a LinkedList with a loop whose next pointers are the same. In a regular single LinkedList (without a loop) each node’s next pointer is unique. So the repeatation of next pointer in a LinkedList is actually indication of a loop. Following figure is an example of a LinkedList with a Loop.

 

Brute-Force Approach: One simple and brute force approach of solving this problem is , start with the first node and check whether there is any node whose next pointer is the current node’s address. If there is a node whose next is same as the current node’s address then that indicates that some other node is pointing to the current node resulting a loop in the linked list. Continue this process for all the nodes in the linked list, now there are 2 possible outcome:

  1. You reaches NULL or the end of the linked list. That means there are no loop in this linked list.
  2. You will identify a loop in the linked list by following the above approach.

Can we do better to solve the problem? Can we use a HashTable to solve the problem?

Using HashTable: The following algorithm using a HashTable can be used to solve the problem. 

  1. Traverse the LinkedList node one by one.
  2. Check whether the node’s address is available in the HashTable or not.
  3. If the node’s address is already available in the hash table, that indicates we have already visited the node earlier and which is a indicator of a loop.
  4. If the node’s address is not present in the hash table, then add it to the hash table.
  5. Continue this process until the reach the end of the linked list or we find a loop.

Time complexity of this algorithm is O(n) for traversing the linked list. And space complexity is O(n) for creating the hash table.

Can we still do better to solve the problem? Yes, we can solve this problem with Time Complexity of O(n)and  without extra memory. The problem can be solved using Floyd cycle detection algorithm. It uses two pointers moving at different speed in the linked list. And both the pointers are expected to meet if there is a loop in the linked list. Otherwise for a regular singly linked list (without a loop) the fast pointer will reaches to the end. Think of a tortoise and a hare running on a track, the faster running hare will catch up with the tortoise if they are running in a Loop. Let us implement the algorithm. Following is the LinkedList ADT we are going to use for the implementation.

Node.java

package com.algo.linkedlist;

/**
 * Created by ardas on 9/14/2018.
 */
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);
 }
}
LinkedList.java
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;
 }
}

Now let us implement the Floyd cycle detection algorithm

package com.algo.linkedlist;

/**
 * Created by ardas on 9/18/2018.
 */
public class FindLoop {

 /**
  * Finding Loop using Floyd cycle detection algorithm
  *
  * @param head
  * @return
  */
 public boolean byFloydCycleDetection(Node head) {
  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)) {
    return true;
   }
  }
  return false;
 }
}

Let us Test the implementation by using 2 LinkedList. Where one linked list has a loop but the other don’t have any loop.

LinkedList linkedListWithLoop = new LinkedList(10, 3);
LinkedList linkedListWithOutLoop = new LinkedList(10);

Now if we apply the algorithm on these 2 linked list, then it will detect the loop for linkedListWithLoop but returns a false to the question hasLoop? for linkedListWithOutLoop

public static void testCircularLinkedList() {
 FindLoop findLoop = new FindLoop();
 LinkedList linkedListWithLoop = new LinkedList(10, 3);
 LinkedList linkedListWithOutLoop = new LinkedList(10);
 System.out.println("LinkedList has Loop by FloydCycleDetection: " 
    + findLoop.byFloydCycleDetection(linkedListWithLoop.head));
 System.out.println("LinkedList has Loop by FloydCycleDetection: " 
    + findLoop.byFloydCycleDetection(linkedListWithOutLoop.head));

}

Download the source code from /algorithm

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself