Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach for Solving
3.1.
Code
3.1.1.
Dry-Run
3.2.
Complexity
4.
Frequently Asked Questions
4.1.
What is a Linked List?
4.2.
What are the different types of Linked List?
4.3.
What is Time Complexity and Space Complexity for Floyd Cycle detection Algorithms?
4.4.
What is Node in a Linked List?
4.5.
Which type of data structure is Linked List?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

First Node Loop in LinkedList

Author Yogesh Kumar
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM
Linked List

Introduction

Linked Lists are one of the most elementary data structures. These are essential tools in any programmer's toolbox. Even during interviews for MNC and Product Based Companies Linked Lists are considered very important and thus it is very advantageous to have a good handle on them and get a good grasp of things. In this article we are going to discuss one of the most common linked list problems. Let's get right to it.

Recommended Topic, Floyds Algorithm

Problem Statement

In this problem, we have given a linked list with a loop in it. We have found the first node of the loop in the Linked List.

To understand the problem statement straightforwardly, let's just take an example and have a more detailed explanation of it.

llustration Image

  1. As we see in the example, we have a linked list above each node containing the address of the next node. This system continues, linearly, as we move towards the last node of the list, i.e., 5, despite having the null value for the end of the node, it contains the address of the next node, i.e., 2 then by the visualization of the figure we can see easily that the here 2, 3, 4 and 5 forming the loop.
  2. From the visualization perspective, we see their loop by joining the contribution of the total 4 nodes.
  3.  Hence, we have assigned the task from the problem statement that we have to return the very first node of the Linked List given.
  4. Looking over the linked list, we see that the very first node is the 2.
  5. Hence our answer for the above image shown is 2.

Also, see Data Structures

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach for Solving

  1. 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.
  2. 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.
  3. Now understand the  Floyd Cycle detection Algorithm in a detailed manner:-
    1. Initialized slow and fast node as head and head.next
    2. 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.
    3. 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.
  4. 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.
  5. 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.
  6. 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;
}

 

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);
      }
  }
}

Dry-Run

Now we dry run the example:-

Illustration Image

  1. Here temp=1, now we have found whether the loop is there or not.
  2. Now declare two nodes slow and fast , assign slow=temp=1 and fast =temp.next=2.
  3. Now fast!=null and slow!=fast ,i.e fast=2 and slow=1 now.
  4. Then slow=slow.next=2 and fast=fast.next.next=4 , hence fast!=null and slow!=fast.
  5. Then slow=slow.next=3 and fast=fast.next.next=2 , hence fast!=null and slow!=fast.
  6. 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.
  7. Now we proceed with finding the first node of the loop. 
  8. Now declare two nodes ptr1 and ptr2 and assign ptr1=temp=1 and ptr2=slow=4.
  9. Now ptr2.next=5 and ptr1=1 , which ptr2.next!=ptr1, now ptr2=ptr2.next=5 and ptr1=ptr1.next=2.
  10. Now ptr2.next=2 and ptr1=2 , where ptr1==ptr2.next , then we are out of the loop.
  11. 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!

Previous article
Find the Sum of Last N Node of given Linked List
Next article
Merge K Sorted Linked Lists
Live masterclass