Detect Loop in Linked List
FREE
Problem Statement
Given a linked list, check whether the linked list is having a loop or not(detect loop in linked list). A cycle exists in a linked list if it contains a node that may be accessed again by following the next pointer.
Example
Input:
Output: True
Explanation: linked list is having 6 nodes and the next pointer of the last node is pointing to the 3rd node which indicates the loop in the linked list.
Input:
Output: True
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Constraints
1<=length of linked list<=10000 1<=Data of Node<=1000
Approach 1: HashSet Approach
We can detect loop in linked list using the HashSet Approach. Traverse the linked list one by one, adding node addresses to a HashMap as you go. If NULL is reached at any point, return False as the end of linked list is reached and it doesn't have any loop. If any previously node address is pointed by the current node, just return True.
Complexity Analysis
Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(N) => N space for storing N nodes in HashMap.
C++ Implementation
Java Implementation
Python Implementation
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Approach 2: Modifying the Linked List Data Structure
We can detect loop in linked list by modifying the Linked List Data Structure. This approach removes the space required for storing values in hashmap, By modifying the linked list data structure. The linked list definition will contain a flag variable that marks the visited node:
- Traverse the Linked list.
- For every node make the flag variable one.
- If the already existing node is accessed return true.
- if null or the end of the linked list is reached return false
Complexity Analysis
Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)
C++ Implementation
Java Implementation
Python Implementation
Approach 3: Floyd’s Cycle
We can detect loop in linked list using the Floyd's Cycle. This is the fastest method for detecting a loop in a linked list:
- Traverse the linked list using two pointers, a fast pointer, and a slow pointer starting from the first node.
- Now in a loop move the fast pointer by 2 nodes and the slow pointer by 1 node.
- If both the pointers point to a same node then loop is detected and return true, else if fast pointer details the end of the linked list return false
Complexity Analysis
Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)
C++ Implementation
Turn Learning into Career Growth
Java Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Python Implementation
Approach 4: Marking visited nodes without modifying the linked list data
We can detect loop in linked list by marking visited nodes without modifying the linked list data. A temporary node is created in this method. Each node that is traversed has its next pointer set to this temporary node:
- The next pointer of a node is used as a visited flag to indicate whether or not the node has been visited.
- Every node is examined to see if the next node is pointing to a temporary node.
- In the case of the loop's first node, this condition will be true the second time we traverse it, indicating that the loop exists.
Complexity Analysis
Time Complexity: O(N) => Only one traversal of loop is needed. Space Complexity: O(1)
C++ Implementation
Java Implementation
Python Implementation
Approach 5: Store length
we can detect loop in linked list by storing length. Two pointers are formed in this method: the first (which always points to the head) and the last. When the last pointer moves, we calculate the number of nodes between the first and last nodes and check whether the current number of nodes is greater than the previous number of nodes; if it is, we move the last pointer; otherwise, we've reached the end of the loop, and we return output accordingly.
Complexity Analysis
Time Complexity: O(N^2) => traversal of pointers * traversal for distance at every iteration. Space Complexity: O(1)
C++ Implementation
Java Implementation
Python Implementation
Conclusion
- A cycle exists in a linked list if it contains a node that may be accessed again by following the next pointer.
- We can follow many approaches for detecting the loop in a linked list:
- Approach 1: HashSet Approach
- Approach 2: modifying the linked list data structure
- Approach 3: Floyd’s Cycle
- Approach 4: Marking visited nodes without modifying the linked list data structure
- Approach 5: Store length
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more