Last Updated on November 9, 2022 by Sumit Kumar
In this article we will learn how to detect the starting node of a loop in the singly linked list. A loop in the singly linked list is a condition that arises when the last node of the linked list does not point to NULL and points to some other node.
How to find first node of loop in a linked list
In this problem, we are given a linked list with a loop. We have to find the first node of loop in a linked list.
Let’s try to understand to find first node of loop in a linked list with the help of examples.
Suppose the given list is:
- According to the problem statement, we need to find first node of loop in a linked list.
- From the linked list, we can see that there is a loop in the linked list starting at a node with value 3 and containing 3 nodes 3, 5, and 7. The last node of the loop points back to the first node of the loop.
- As the node with value 3 is the first node of the loop, so we will return 3 as output.
If the given linked list is:
- In this case, our loop comprises 6, 8, and 10 and the node with value 6 is the first node of the loop. So we will output 6.
Now, I think from the above examples, it is clear to find starting point of loop in linked list.
Before moving to the approach section to find first node of loop in a linked list, try to think about how you can approach to find starting point of loop in linked list. What is the first thing that comes to your mind?
The very first thing that comes to mind is loop detection. Correct, but we can also use hashing to find first node of loop in a linked list.
- The hashing solution will require O(n) space for the creation of the hash table, so we are first going to look at hashing approach, and then jump to the efficient loop detection approach.
Let us glance at the approach to get a clear look.
Approach and Algorithm to find starting point of loop in linked list(Hashing)
In this approach, we will use hashing to solve the problem. Well, how can hashing help us?
- If we notice carefully, the first node of the loop is the first element that will appear twice while traversing the linked list with a loop.
1) We will first create a set, which will store the addresses of the nodes.
2) Now, we will traverse the given linked list. For every node, we will check if that node is present in the set or not.
- If it is not present, then we will simply insert it into the set.
- If the node is present in the set, it means that the current node is the first node of the loop. ThAs the first node of the loop will be the first repeating node while traversing the list. So, if the node is present in the set, we will simply return that node.
This approach will work fine for the program to detect the starting node of a loop in the single linked list, but it requires extra O(n) space. So, now the main question is can we optimize this space?
- The answer is yes, and we will see how we can optimize this space in the next approach find starting point of loop in linked list .
Our next approach uses Floyd’s Cycle Detection algorithm.
Approach and Algorithm find starting point of loop in linked list(Floyd’s Cycle Detection)
Our approach will be simple to find first node of loop in a linked list:
- Firstly, we have to detect the loop in the given linked list.
- For detecting a loop in any linked list, we know the most efficient algorithm is the Floyd Cycle detection Algorithm.
- In Floyd’s cycle detection algorithm, we initialize 2 pointers, slow and fast.
- Both initially point to the head of the list.
- The slow pointer jumps one place and the fast pointer jumps 2 places.
- The node at which the slow and fast pointer meet is a loop node.
- Now, after finding the loop node:
- We will make 2 pointers ptr1 and ptr2, which will point to that loop node.
- We will also initialize a variable to find the length of the loop. Now, how will we find the length of this loop?
- ptr2 will be fixed, and we will increment ptr1 till it meets ptr2. As both are at the same position currently, when ptr1 will meet ptr2, the whole loop would’ve been traversed, and we will get the length k.
- Now, as we have the length of the loop, we will make ptr1 and ptr2 point to the head again.
- Now, we will shift ptr2 by k places.
- After shifting, we will move both ptr1 and ptr2 simultaneously (taking 1 jump). The node at which ptr1 and ptr2 will meet will be the first node of the loop.
- After finding the first node of the loop, we will return it.
Dry Run to find first node of loop in a linked list
Approach and Algorithm to find starting point of loop in linked list(More Optimized Approach)
In the previous method, after finding the loop node, we were also running a for loop to find the length of the loop in the linked list. Can we find the first node of the loop without finding the length of the loop?
- The answer is Yes, and in this approach, we will see how we can do it.
This method will be very much similar to the previous one, but here we will try to avoid finding the length of the loop.
- Similar to the previous method, we will find the loop node using Floyd Cycle detection Algorithm.
- After finding the loop node, we will initialize the slow pointer to the head of the linked list and the fast pointer will remain at its position.
- Now we will start moving the fast and slow pointer one node at a time until they meet each other.
- The node at which slow and fast meets will be the starting point or say the first node of the loop.
Now, let’s see the dry run for this approach.
Dry Run to find starting point of loop in linked list
Code Implementation to find first node of loop in a linked list
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
struct Node {
int key;
struct Node* next;
};
/* Using this we are creating a new list node */
struct Node* newNode(int x)
{
struct Node* node = malloc(sizeof(struct Node*));
node->key = x;
node->next = NULL;
return node;
}
/* Using this function we will be printing the list */
void printList(struct Node* head)
{
while (head != NULL) {
printf("%d ",head->key);
head = head->next;
}
printf("\n");
}
/* Using this function we will find and return the first node of loop in the linked list */
struct Node* firstnode(struct Node* head)
{
if (head == NULL || head->next == NULL)
return NULL;
struct Node *slow = head;
struct Node *fast = head;
slow = slow->next;
fast = fast->next->next;
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
if (slow != fast)
return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
int main()
{
struct Node* head = newNode(1);
head->next = newNode(0);
head->next->next = newNode(3);
head->next->next->next = newNode(0);
head->next->next->next->next = newNode(1);
head->next->next->next->next->next = head->next;
struct Node* res = firstnode(head);
if (res == NULL)
printf("Loop does not exist");
else
printf("Loop starting node is %d",res->key);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
/* Structure of a linked list node */
struct Node {
int key;
struct Node* next;
};
/* Using this we are creating a new list node */
Node* newNode(int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
/* Using this function we will be printing the list */
void printList(Node* head)
{
while (head != NULL) {
cout << head->key << " ";
head = head->next;
}
cout << endl;
}
/* Using this function we will find and return the first node of loop in the linked list */
Node* firstnode(Node* head)
{
if (head == NULL || head->next == NULL)
return NULL;
Node *slow = head, *fast = head;
slow = slow->next;
fast = fast->next->next;
while (fast && fast->next) {
if (slow == fast)
break;
slow = slow->next;
fast = fast->next->next;
}
if (slow != fast)
return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
int main()
{
Node* head = newNode(1);
head->next = newNode(0);
head->next->next = newNode(3);
head->next->next->next = newNode(0);
head->next->next->next->next = newNode(1);
head->next->next->next->next->next = head->next;
Node* res = firstnode(head);
if (res == NULL)
cout << "Loop does not exist";
else
cout << "Loop starting node is " << res->key;
return 0;
}
import java.util.*;
public class PrepBytes{
/* Structure of a linked list node */
static class Node
{
int key;
Node next;
};
/* Using this we are creating a new list node */
static Node newNode(int key)
{
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
/* Using this function we will be printing the list */
static void printList(Node head)
{
while (head != null){
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
/* Using this function we will find and return the first node of loop in the linked list */
static Node firstnode(Node head)
{
if (head == null || head.next == null)
return null;
Node slow = head, fast = head;
slow = slow.next;
fast = fast.next.next;
while (fast != null && fast.next != null){
if (slow == fast)
break;
slow = slow.next;
fast = fast.next.next;
}
if (slow != fast)
return null;
slow = head;
while (slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
public static void main(String[] args)
{
Node head = newNode(1);
head.next = newNode(0);
head.next.next = newNode(3);
head.next.next.next = newNode(0);
head.next.next.next.next = newNode(1);
head.next.next.next.next.next = head.next;
Node res = firstnode(head);
if (res == null)
System.out.print("Loop does not exist");
else
System.out.print("Loop starting node is " + res.key);
}
}
class Node:
def __init__(self, key):
self.key = key
self.next = None
def newNode(key):
temp = Node(key)
return temp
def printList(head):
while (head != None):
print(head.key, end = ' ')
head = head.next
print()
def firstNode(head):
if (head == None or head.next == None):
return None
slow = head
fast = head
slow = slow.next
fast = fast.next.next
while (fast and fast.next):
if (slow == fast):
break
slow = slow.next
fast = fast.next.next
if (slow != fast):
return None
slow = head
while (slow != fast):
slow = slow.next
fast = fast.next
return slow
if __name__=='__main__':
head = newNode(1)
head.next = newNode(0)
head.next.next = newNode(3)
head.next.next.next = newNode(0)
head.next.next.next.next = newNode(1)
head.next.next.next.next.next = head.next
res = firstNode(head)
if (res == None):
print("Loop does not exist")
else:
print("Loop starting node is " +
str(res.key))
Output
Loop starting node is 0
Time Complexity: O(n), as no nested traversal is needed.
Conclusion:
So, in this article, we have explained the most efficient approach to finding the first node of a loop in a linked list or detecting the starting node of a loop in a single linked list. Multiple concepts have been used here, so it makes this question an important one for coding interviews.
FAQs related to Bubble Sort in Linked List
- How do you find the starting point of the loop in the linked list?
- We will first create a set, which will store the addresses of the nodes.
- We will traverse the linked list and for every given node, we will check If that node is present or not.
- If it is not present then we will insert it into the set and if the node is present it means that the current node is starting node of the loop in the linked list.
- How do you find the loop in the linked list?
We will find the starting point of the linked list as follows:
A loop can be detected by using a slow and fast pointer algorithm. In this algorithm, a slow pointer moves by one node and a fast pointer moves by two nodes and at any point, when the slow and fast pointer points to the same node, it means the loop is detected at that node and if the fast pointer reaches to end, it means linked list doesn’t contain the loop.