Problem Statement
Given a linked list, we aim to determine whether there exists a cycle (loop) within the list. A cycle occurs when a node points to a previously visited node, creating a loop in the list.
Examples
Example 1:
Input: List = 1->2->3->4->5
Output: True
Explanation: The last node with the value of 5 has its next pointer pointing back to a previous node with the value of 3. This has resulted in a loop, hence we return true.
Example 2:
Input: List: 1->3->7->4->nullptr
Output: false
Explanation: No loop is present in the linked list.Approaches
1️⃣ Brute Force Approach
A loop in a linked list occurs when there's a node that, when followed, brings back to it, indicating a closed loop in the list.
Hence its important to keep track of nodes that we have already been visited so that loops can be detected. One common way to do this is by using hashing.
Algorithm:
- Traverse the list using the traversal technique of assigning a temp node to the head and iterating by moving to the next element till we reach null.
- While traversing, keep a track of the visited nodes in the data structure.
- If a previously visited node is encountered again, that proves that there is a loop in the linked list hence return true.
- If the traversal is completed, and we reach the last point of the List which is null, it means there was no loop, hence we return false.
Dry Run:
Initialization:
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| | |
+------------+---------------+
| | |
+------------+---------------+
HashMapFirst Iteration:
current
|
v
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| | |
+------------+---------------+
| | |
+------------+---------------+
HashMap
current = node(1)
Since it is not present in the HashMap
So, add the node as the key and value as 1.Second Iteration:
current
|
v
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| Node 1 | 1 |
+------------+---------------+
| | |
+------------+---------------+
HashMap
current = node(2)
Since it is not present in the HashMap
So, add the node as the key and value as 1.Third Iteration:
current
|
v
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| Node 1 | 1 |
+------------+---------------+
| Node 2 | 1 |
+------------+---------------+
HashMap
current = node(3)
Since it is not present in the HashMap
So, add the node as the key and value as 1.Fourth Iteration:
current
|
v
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| Node 1 | 1 |
+------------+---------------+
| Node 2 | 1 |
+------------+---------------+
| Node 3 | 1 |
+------------+---------------+
HashMap
current = node(4)
Since it is not present in the HashMap
So, add the node as the key and value as 1.Fifth Iteration:
+-----+ +-----+ +-----+ +-----+
| 1 |-->| 2 |-->| 3 |-->| 4 |------+
+-----+ +-----+ +-----+ +-----+ |
^ |
| |
+-----------------------------+
^
|
current
+------------+---------------+
| key (Node) | value(1 or 0) |
+------------+---------------+
| Node 1 | 1 |
+------------+---------------+
| Node 2 | 1 |
+------------+---------------+
| Node 3 | 1 |
+------------+---------------+
| Node 4 | 1 |
+------------+---------------+
HashMap
current = node(2)
Since node(2) is present in the HashMap,
It means there is loop in LL.
Return trueCode:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Node class represents a
// node in a linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list
Node* next;
// Constructor with both data
// and next node as parameters
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data as
// a parameter, sets next to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};
// function to detect loop in linked list
bool detectLoop(Node* head) {
// Initialize a pointer 'temp'
// at the head of the linked list
Node* temp = head;
// Create a map to keep track of
// encountered nodes
std::unordered_map<Node*, int> nodeMap;
// Step 2: Traverse the linked list
while (temp != nullptr) {
// If the node is already in the
// map, there is a loop
if (nodeMap.find(temp) != nodeMap.end()) {
return true;
}
// Store the current node
// in the map
nodeMap[temp] = 1;
// Move to the next node
temp = temp->next;
}
// Step 3: If the list is successfully traversed
// without a loop, return false
return false;
}
int main() {
// Create a sample linked list
// with a loop for testing
Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);
Node* fifth = new Node(5);
head->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
// Create a loop
fifth->next = third;
// Check if there is a loop
// n the linked list
if (detectLoop(head)) {
cout << "Loop detected in the linked list." << endl;
} else {
cout << "No loop detected in the linked list." << endl;
}
// Clean up memory (free the allocated nodes)
delete head;
delete second;
delete third;
delete fourth;
delete fifth;
return 0;
}
// Output
Loop detected in the linked list.Complexity Analysis:
- Time Complexity:
O(n * 2 * log(n))- The algorithm traverses the linked list once, performing hashmap insertions and searches in the while loop for each node.
- The insertion and search operations in the unordered_map have a worst-case time complexity of
O(log(n)). As the loop iterates through n nodes, the total time complexity is determined by the product of the traversalO(n)
- Space Complexity:
O(n)- Because of the hashmap/dictionary to store encountered nodes, which can take up to
O(n)additional space, wherenis the number of nodes in the list.
- Because of the hashmap/dictionary to store encountered nodes, which can take up to
2️⃣ Optimal Approach
Brute force approach uses O(n) additional memory space, which can become quite large as the linked list length grows. To enhance efficiency, the Tortoise and Hare algorithm is introduced as an optimization.
The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. If there is a cycle in the list, the fast pointer will eventually catch up the slow pointer inside the loop.
Algorithm:
- Initialize two pointer, slow and fast, both pointing to the head of the linked list.
- While traversing the list:
- Move the slow pointer one step forward.
- Move the fast pointer two steps forward.
- If the fast pointer reaches the end of list (
nullptr), there is no cycle, so return false. - If the slow pointer and fast pointer meet at any point, there is a cycle, so return true.
Code:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Node class represents a
// node in a linked list
class Node {
public:
// Data stored in the node
int data;
// Pointer to the next node in the list
Node* next;
// Constructor with both data
// and next node as parameters
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data as
// a parameter, sets next to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to detect a loop in a linked
// list using the Tortoise and Hare Algorithm
bool detectCycle(Node* head) {
if (head == nullptr) {
return false;
}
// Initialize two pointers, slow and fast,
// to the head of the linked list
Node* slow = head;
Node* fast = head;
// Step 2: Traverse the linked list with
// the slow and fast pointers
while (fast != nullptr && fast->next != nullptr) {
// Move slow one step
slow = slow->next;
// Move fast two steps
fast = fast->next->next;
// Check if slow and fast pointers meet
if (slow == fast) {
return true; // Loop detected
}
}
// If fast reaches the end of the list,
// there is no loop
return false;
}
int main() {
// Create a sample linked list
// with a loop for testing
Node* head = new Node(1);
Node* second = new Node(2);
Node* third = new Node(3);
Node* fourth = new Node(4);
Node* fifth = new Node(5);
head->next = second;
second->next = third;
third->next = fourth;
fourth->next = fifth;
// Create a loop
fifth->next = third;
// Check if there is a loop
// n the linked list
if (detectCycle(head)) {
cout << "Loop detected in the linked list." << endl;
} else {
cout << "No loop detected in the linked list." << endl;
}
// Clean up memory (free the allocated nodes)
delete head;
delete second;
delete third;
delete fourth;
delete fifth;
return 0;
}
// Output
Loop detected in the linked list.Complexity Analysis:
- Time Complexity:
O(n)- This is because in the worst case scenario, the fast pointer, which moves quicker, will either reach the end of the list (in case of no loop) or meet the slow pointer (in case of loop) in a linear time relative to the length of the list.
- Space Complexity:
O(1)