Given a singly linked list, check if the linked list has a loop (cycle) or not. A loop means that the last node of the linked list is connected back to a node in the same list.
Using HashSet – O(n) Time and O(n) Space:
To solve the issue, take the actions listed below:
- To hold the addresses (or references) of the visited nodes, initialize a blank HashSet.
- Check to see if each node’s address (or reference) is already in the HashSet as you proceed through the linked list from the head.
- Return false since there is no loop if the node is NULL, which denotes the end of the linked list.
- Add the node’s address to the HashSet if it isn’t already there.
- There is a cycle (loop) in the list if the node’s address is already in the HashSet. Return true in this instance.
- The application of the aforementioned strategy is seen below:
C++
// C++ program to detect loop in a linked list
// using hashset
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = nullptr;
}
};
// Function that returns true if there is a loop in linked
// list else returns false.
bool detectLoop(Node* head) {
unordered_set<Node*>st;
// loop that runs till the head is nullptr
while (head != nullptr) {
// If this node is already present
// in hashmap it means there is a cycle
// (Because you will be encountering the
// node for the second time).
if (st.find(head) != st.end())
return true;
// If we are seeing the node for
// the first time, insert it in hash
st.insert(head);
head = head->next;
}
return false;
}
int main() {
// Create a hard-coded linked list:
// 10 -> 20 -> 30 -> 40 -> 50 -> 60
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
head->next->next->next = new Node(40);
head->next->next->next->next = new Node(50);
head->next->next->next->next->next = new Node(60);
head->next->next->next->next = head;
if (detectLoop(head))
cout << "true";
else
cout << "false";
return 0;
}
Java
// Java program to detect loop in a linked list
// using hashset
import java.util.HashSet;
import java.util.Set;
class Node {
int data;
Node next;
Node(int x) {
this.data = x;
this.next = null;
}
}
class GfG {
// Function that returns true if there is a loop in
// linked list else returns false.
static boolean detectLoop(Node head) {
Set<Node> st = new HashSet<>();
// loop that runs till the head is null
while (head != null) {
// If this node is already present
// in hashmap it means there is a cycle
// (Because you will be encountering the
// node for the second time).
if (st.contains(head))
return true;
// If we are seeing the node for
// the first time, insert it in hash
st.add(head);
head = head.next;
}
return false;
}
public static void main(String[] args) {
// Create a hard-coded linked list:
// 10 -> 20 -> 30 -> 40 -> 50 -> 60
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
head.next.next.next.next.next = new Node(60);
head.next.next.next.next = head;
if (detectLoop(head))
System.out.println("true");
else
System.out.println("false");
}
}Python
# Python program to detect loop
# in the linked list using hashset
class Node:
def __init__(self, x):
self.data = x
self.next = None
# Function that returns true if there is a loop in linked
# list else returns false.
def detect_loop(head):
st = set()
# loop that runs till the head is None
while head is not None:
# If this node is already present
# in hashmap it means there is a cycle
# (Because you will be encountering the
# node for the second time).
if head in st:
return True
# If we are seeing the node for
# the first time, insert it in hash
st.add(head)
head = head.next
return False
# Create a hard-coded linked list:
# 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head.next.next.next = Node(40)
head.next.next.next.next = Node(50)
head.next.next.next.next.next = Node(60)
head.next.next.next.next = head
if detect_loop(head):
print("true")
else:
print("false")JS
// JavaScript program to detect loop in a linked list
// using hashset
class Node {
constructor(x) {
this.data = x;
this.next = null;
}
}
// Function that returns true if there is a loop in
// linked list else returns false.
function detectLoop(head) {
let st = new Set();
// loop that runs till the head is null
while (head !== null) {
// If this node is already present
// in hashmap it means there is a cycle
// (Because you will be encountering the
// node for the second time).
if (st.has(head))
return true;
// If we are seeing the node for
// the first time, insert it in hash
st.add(head);
head = head.next;
}
return false;
}
// Create a hard-coded linked list:
// 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
head.next.next.next.next.next = new Node(60);
head.next.next.next.next = head;
if (detectLoop(head))
console.log("true");
else
console.log("false");Output
true
Time complexity: O(n), where n is the number of nodes in the Linked List.
Auxiliary Space: O(n), n is the space required to store the value in the hash set.