- 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
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->
- if we start traversing the single linked list, it will never terminate.
- 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 |