Floyd’s cycle detection algorithm to check loop in single linked list

• Given a single linked list, we would like to find out whether loop or cycle exists in a single linked list.
•  We will iterate through single linked list using non-recursive algorithm.
• We have discussed similar problems
  • find the middle element in single linked list
  • find the nth element from last in a single linked list.

What is cycle or loop in a single linked list ?

Let us take an example to elaborate the problem statement. We have shown the single linked list in Fig 1.

• The single list shown in Fig 1 is not null terminated.
  • if we start traversing the single linked list, it will never terminate.
    • 20 -> 25-> 30-> 35-> 40 -> 45-> 50-> 55-> 30-> 35-> 40 -> 45-> 50-> 55-> 
• The single linked list traversal will always remain in infinite loop.
  • This is very important point to detect whether loop exist in the linked list.

Floyd’s cycle detection algorithm to find loop in single linked list.

Step 1: Floyd’s cycle detection algorithm

• Take slow and fast pointer.
• slow and fast pointer will point to head of linked list
• slow pointer will jump by 1 node.
• fast pointer will jump by 2 nodes.

Step 2: Floyd’s cycle detection algorithm

• slow pointer jumped by 1 node.
• fast pointer jumped by 2 node.

Step 3: Floyd’s cycle detection algorithm

• fast pointer keep on moving by two nodes
• slow pointer will keep in jumping by 1 node

Step 4: Floyd’s cycle detection algorithm

• Keep on performing the step 3
• We will encounter the situation where slow == fast
  • Signifies that the loop exists in a single linked list
• If we did not encounter slow == fast
  • Linked list does not have loop

Time complexity of algorithm is O (n).

Program – Floyd’s cycle detection algorithm to find loop in single linked list

1.) DetectLoop Class:

• We are passing the head of single linked list, to isLooped method.
• isLooped method is used to detect, whether loop exists in a single linked list.

package org.learn.Question;

public class DetectLoop {

	public static boolean isLooped(Node head) {
		if (null == head) {
			System.out.println("Single linked list is empty");
			return false;
		}

		Node slow = head;
		Node fast = head;
		while (slow != null && fast != null && fast.next != null) {

			fast = fast.next;
			if (slow == fast) {
				System.out.println("Loop exists in a single linked list");
				return true;
			}
			fast = fast.next;
			if (slow == fast) {
				System.out.println("Loop exists in a single linked list");
				return true;
			}
			slow = slow.next;
		}
		System.out.println("No loop exists in a single linked list");
		return false;
	}

	public static Node insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
		return head.next;
	}
}

2.) DetechLoopClient Class:

• We are creating a single linked list in main method.
• We are calling DetectLoop.isLooped method, to check whether loop exists in a single linked list

package org.learn.Client;

import org.learn.Question.DetectLoop;
import org.learn.Question.Node;

public class DetechLoopClient {
	
	public static void main(String[] args) {
		int[] data = { 30, 35, 40, 45, 50, 55 };
		Node node30 = new Node(data[0]);
		Node node = null;
		
		for (int count = 1; count < data.length; count++) {
			node = DetectLoop.insert(node30, data[count]);
		}
		
		node.next = node30;
		node = new Node(20);
		node.next = new Node(25);
		node.next.next = node30;
		
		DetectLoop.isLooped(node);
	}
}

3.) Node Class:

• Node class representing the nodes of a single linked list

package org.learn.Question;

public class Node {
	public int data;
	public Node next;

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

Output – Floyd’s cycle detection algorithm to check loop in a single linked list

Loop found in linked list

Download Code – floyd algorighm to detect loop / cyle exists in single linked list