First Node Loop in LinkedList

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.

  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.

 

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 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:-

  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.

FAQ

1). What is a Linked List?

Ans: A linked list is a collection of nodes where each node is connected to the next node through a pointer.

2). What are the different types of Linked List?

Ans: Singly, Doubly, Circular, Doubly Circular Linked List.

3). What is Time Complexity and Space Complexity for Floyd Cycle detection Algorithms?

Ans: Time Complexity is O(N), and Space Complexity is O(1).

4). What is Node in a Linked List?

Ans:  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.

5). Which type of data structure is Linked List?

Ans: A linked list is a linear data structure where the elements are not stored at contiguous memory locations.

 

Key TakeAway

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.

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think