So the question given is to check if the Given Linked list is having a cycle or Not, and if there is a cycle then we need to print the start of the Loop in a cyclic linked list.
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.
once we find the meeting point of slow and fast pointer we will point the slow pointer to head and will again run the loop, this time we will traverse both slow and fast pointer only one step at once.
Java Solution of the above 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(GetMeetingNode(node1));
}
private static int GetMeetingNode(ListNode ll) {
ListNode slowPtr = ll;
ListNode fastPtr = ll;
while(true){
if(fastPtr == null || fastPtr.next == null)
return -1;
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr == fastPtr)
break;
}
slowPtr = ll;
while(true) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next;
if(slowPtr == fastPtr)
return slowPtr.data;
}
}
}
output:
3The time complexity of the above solution is O(n) and Space complexity is O(1)
