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
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
bool hasLoop(Node* head) {
Node* temp = head;
set<Node*> hashSet;
while (temp != null) {
if (hashSet.find(temp) != hashSet.end()) {
return true;
}
hashSet[temp]++;
temp = temp->next;
}
return false;
}
Java Implementation
public boolean hasLoop(ListNode head) {
Set<ListNode> hashSet = new HashSet<>();
while (head != null) {
if (hashSet.contains(head)) {
return true;
}
hashSet.add(head);
head = head.next;
}
return false;
}
Python Implementation
def hasLoop(head):
temp = head
hashSet = set()
while temp is not None:
if temp in hashSet:
return True
hashSet.add(temp)
temp = temp.next
return False
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
/* Link list node definition */
struct Node {
int data;
struct Node* next;
int vis;
};
bool hasLoop(struct Node* head){
while (head != NULL) {
// If vis is 1 then it is already visited, return true
if (head->vis == 1)
return true;
// If we are seeing the node first time, vis = 1
head->vis = 1;
head = head->next;
}
return false;
}
Java Implementation
// Link list node definition
static class Node
{
int data;
Node next;
int vis;
};
static boolean hasLoop(Node head)
{
while (head != null)
{
// If vis is 1 then it is already visited, return true
if (head.vis == 1)
return true;
// If we are seeing the node first time, vis = 1
head.vis = 1;
head = head.next;
}
return false;
}
Python Implementation
# Link list node definition
class Node:
def __init__(self):
self.data = 0
self.next = None
self.vis = 0
def hasLoop(head):
while (head != None):
# If vis is 1 then it is already visited, return true
if (head.vis == 1):
return True;
# If we are seeing the node first time, vis = 1
head.vis = 1;
head = head.next;
return False;
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
bool hasLoop(Node* head)
{
Node *slow = head, *fast = head;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
Java Implementation
static boolean hasLoop(Node head)
{
Node slow = head, fast = head;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
Python Implementation
def hasLoop(head):
slow = head
fast = head
while(slow and fast and fast.next):
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
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
bool hasLoop(Node* head)
{
// Temporary node
Node* temp = new Node;
while (head != NULL) {
// If End is reached return false
if (head->next == NULL) {
return false;
}
// if next is pointing to temp loop exists
if (head->next == temp) {
return true;
}
// Store the pointer to the next node
Node* next = head->next;
// Make next point to temp
head->next = temp;
// Getting the next node in the list
head = next;
}
return False;
}
Java Implementation
static boolean hasLoop(Node head)
{
// Creating a temporary node
Node temp = new Node();
while (head != null) {
// If End is reached return false
if (head.next == null) {
return false;
}
// if next is pointing to temp loop exists
if (head.next == temp) {
return true;
}
// Store the pointer to the next node
Node nex = head.next;
// Make next point to temp
head.next = temp;
// Getting the next node in the list
head = nex;
}
return false;
}
Python Implementation
def hasLoop(head):
# Creating a temporary node
temp = ""
while (head != None):
# If End is reached return false
if (head.next == None):
return False
# if next is pointing to temp loop exists
if (head.next == temp):
return True
# Store the pointer to the next node
nex = head.next
# Make next point to temp
head.next = temp
# Geting the next node in the list
head = nex
return False
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
int distance(Node* start, Node* end)
{
Node* temp = start;
// initializing the counter variable by 0
int count = 0;
// Counting the distance
while (temp != end) {
count += 1;
temp = temp->next;
}
return count + 1;
}
bool hasLoop(Node* head)
{
// Creating a temporary node
Node* temp = new Node;
Node *first, *last;
first = head;
last = head;
int currentLength = 0;
// prev_length stores no of nodes between previous position of first and last
int previousLength = -1;
while (currentLength > previousLength && last != NULL) {
// set the value of previousLength to current length
previousLength = currentLength;
// currentLength between the first and last node passed in distance function
currentLength = distance(first, last);
// Increment last node
last = last->next;
}
if (last == NULL) {
// Return false if last node is reached
return false;
}
else {
return true;
}
}
Java Implementation
static int distance(Node start, Node end)
{
Node temp = start;
// initializing the counter variable by 0
int count = 0;
// Counting the distance
while (temp != end) {
count += 1;
temp = temp.next;
}
return count + 1;
}
static boolean hasLoop(Node head)
{
// Create a temporary node
Node temp = new Node();
Node first, last;
first = head;
last = head;
int currentLength = 0;
// prev_length stores no of nodes between previous position of first and last
int previousLength = -1;
while (currentLength > previousLength && last != null) {
// set the value of previousLength to current length
previousLength = currentLength;
// currentLength between the first and last node passed in distance function
currentLength = distance(first, last);
// Increment last node
last = last.next;
}
if (last == null)
{
// Return false if last node is reached
return false;
}
else
{
return true;
}
}
Python Implementation
def distance(first, last):
# counts no of nodes between first and last
counter = 0
temp = first
while (temp != last):
counter = counter + 1
temp = temp.next
return counter + 1
def detectLoop(head):
# Create a temporary node
temp = ""
first = head;
last = head;
current_length = 0
# prev_length stores no of nodes between previous position of first and last
prev_length = -1
while (current_length > prev_length and last != None) :
# set prev_length to current length then update the current length
prev_length = current_length
# distance is calculated
current_length = distance(first, last)
# last node points the next node
last = last.next;
if (last == None) :
return False
else :
return True
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
