Approach for Solving
- We are going to solve the problem by taking two ideas, just find a loop for corner case, if it exists or not, if it doesn't exist then, nothing we are going to proceed with, if its loop gets found in the loop, then we move further with the idea of finding the first node in it.
-
Now for detecting whether the loop exists in the given linked list or not, we just have to use the Floyd's Cycle Detection Algorithm for it.
-
Now understand the Floyd Cycle detection Algorithm in a detailed manner:-
- Initialized slow and fast node as head and head.next
- For the next, while we iterated till fast!=null and slow!=fast and moved the node for slow to slow.next by one step and fast to fast.next.next by two steps.
- Now then, we check for the point if slow==fast, as simply we have slow and fast meet up then we have a loop. Otherwise, if the end of the loop is slow!=fast, we have no loop there.
- As we see now, we have all clear ideas about whether there is a loop exit or not. If the loop exists, then we are coding part of step 4 work. Else it returns null step 4 itself.
- Now for finding the first node of the existing loop part, we take two extra pointer nodes as one assigned with slow pointer and the other with the head or temp.
- We again run a loop while with condition ptr2.next!=ptr1, moving the node of ptr1 to next, same for ptr2.
Node ptr1=temp;
Node ptr2=slow;
while(ptr2.next!=ptr1){
ptr1=ptr1.next;
ptr2=ptr2.next;
}

You can also try this code with Online Java Compiler
Run Code
7. Now we return the ptr1 pointer, where we get the first nodes of the loop found in the Linked List.
Code
public class first_node {
static class Node{
int data;
Node next;
};
static Node newNode(int data){
Node temp=new Node();
temp.data=data;
temp.next=null;
return temp;
}
static Node first_node_of_loop(Node temp){
// Detecting the Loop in a Linked List
Node slow=temp;
Node fast=temp.next;
while(fast!=null && fast.next!=null && slow!=fast){
slow=slow.next;
fast=fast.next.next;
}
// Condition for the No Loop
if(slow!=fast){
return null;
}
// Finding the first node of the Loop
Node ptr1=temp;
Node ptr2=slow;
while(ptr2.next!=ptr1){
ptr1=ptr1.next;
ptr2=ptr2.next;
}
return ptr1;
}
public static void main(String[] args){
Node temp=newNode(1);
temp.next=newNode(2);
temp.next.next=newNode(3);
temp.next.next.next=newNode(4);
temp.next.next.next.next=newNode(5);
// Condition for the Testing
temp.next.next.next.next.next=temp.next;
Node ans=first_node_of_loop(temp);
if(ans==null){
System.out.print("Loop is not Found");
}
else{
System.out.println("First Node of the Loop is "+ " "+ans.data);
}
}
}

You can also try this code with Online Java Compiler
Run Code
Dry-Run
Now we dry run the example:-

- Here temp=1, now we have found whether the loop is there or not.
- Now declare two nodes slow and fast , assign slow=temp=1 and fast =temp.next=2.
- Now fast!=null and slow!=fast ,i.e fast=2 and slow=1 now.
- Then slow=slow.next=2 and fast=fast.next.next=4 , hence fast!=null and slow!=fast.
- Then slow=slow.next=3 and fast=fast.next.next=2 , hence fast!=null and slow!=fast.
- Then slow=slow.next=4 and fast=fast.next.next=4, now we have fast!=null, but we have slow==fast, then we get sure now that the loop must be there, that is for sure.
- Now we proceed with finding the first node of the loop.
- Now declare two nodes ptr1 and ptr2 and assign ptr1=temp=1 and ptr2=slow=4.
- Now ptr2.next=5 and ptr1=1 , which ptr2.next!=ptr1, now ptr2=ptr2.next=5 and ptr1=ptr1.next=2.
- Now ptr2.next=2 and ptr1=2 , where ptr1==ptr2.next , then we are out of the loop.
- We return the ptr1, which returns the first node of the loop, i.e., 2, our expected result.
Complexity
Now talking about the Time and Space complexity of the Coding as we see it the Linked List, which is presented through getting contact over the dry run part, we see that we just have the iteration over the length size of the linked list, which sees O(L) and for the next part we have iteration for finding the first node is “diff=(length of linked list - length of loop).” If we get into it, overall, we say Time Complexity is L+diff, so in general, it’s O(L) where L is the length of a linked list and diff=(length of linked list - length of loop).
Now taking over the Space Complexity, we are not using the extra space other than the currently linked list is given; we are using the same Linked List, forgetting all the operations done over there, we are declaring extra node for just pointing the same linked list node by a different name, just for ease for the problem to solve smoothly. So there we are, just taking O(1) constant Space extra for solving the problem.
Frequently Asked Questions
What is a Linked List?
A linked list is a collection of nodes where each node is connected to the next node through a pointer.
What are the different types of Linked List?
Singly, Doubly, Circular, Doubly Circular Linked List.
What is Time Complexity and Space Complexity for Floyd Cycle detection Algorithms?
Time Complexity is O(N), and Space Complexity is O(1).
What is Node in a Linked List?
A node contains two fields, i.e., data stored at that particular address and the pointer, which has the address of the next node in the memory. The last node of the list contains a pointer to the null.
Which type of data structure is Linked List?
A linked list is a linear data structure where the elements are not stored at contiguous memory locations.
Conclusion
In this blog, we learn about the Concept of LinkedList using the problem statement to find the first node of the Loop by utilizing the famous Floyd Cycle detection Algorithm to detect the cycle or loop in the Linked List and then find the first node in the loop part.
If you are confident of the topic and want to submit it on our coding platform then you can check here First Node Loop in Linked List.
Recommended Reading:
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!