So the question given is to check if the Given Linked list is having a cycle or Not?
We will be using Floyd Cycle to find the solution of the given problem.
It uses 2 pointers moving at different speeds to walking the linked list. Once they enter the loop they are expected to meet, which denotes that there is a loop. This works because the only way a faster moving pointer would point to the same location as a slower moving pointer is if somehow the entire list or a part of it is circular.
Java Solution for the following problem is given below:
package askgif.linkedlist;
class ListNode{
public int data;
public ListNode next;
};
public class CircularNodeExist {
public static void main(String[] args) {
ListNode node1 = new ListNode();
ListNode node2 = new ListNode();
ListNode node3 = new ListNode();
ListNode node4 = new ListNode();
ListNode node5 = new ListNode();
ListNode node6 = new ListNode();
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node5.data = 5;
node6.data = 6;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node3;
System.out.println(IsLoopExist(node1));
}
private static Boolean IsLoopExist(ListNode ll) {
ListNode slowPtr = ll;
ListNode fastPtr = ll;
while(true){
if(fastPtr == null || fastPtr.next == null)
return false;
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr == fastPtr)
return true;
}
}
}
output:
trueThe time complexity of the above solution is O(n) as we are traversing through the entire linked list once.
Space Complexity: O(1)
