In this article, we will solve the most asked interview question: Detect a Cycle in a Linked List
Problem Statement: Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Return true if there is a cycle in the linked list. Otherwise, return false.
Examples:
Example 1: Input: Head = [1,2,3,4] Output: true Explanation: Here, we can see that we can reach node at position 1 again by following the next pointer. Thus, we return true for this case.
Example 2: Input: Head = [1,2,3,4] Output: false Explanation: Neither of the nodes present in the given list can be visited again by following the next pointer. Hence, no loop exists. Thus, we return false.
Solution: Hashing
Approach:
We need to keep track of all the nodes we have visited till now so that once we visit the same node again we can say that a cycle is detected. The process is as follows:
- Use a hash table for storing nodes.
- Start iterating through the lists.
- If the current node is present in the hash table already, this indicates the cycle is present in the linked list and returns true.
- Else move insert the node in the hash table and move ahead.
- If we reach the end of the list, which is NULL, then we can say that the given list does not have a cycle in it and hence we return false.
Dry Run:
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node in the list
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
head = newNode;
return;
}
node* temp = head;
while(temp->next != NULL) temp = temp->next;
temp->next = newNode;
return;
}
//utility function to create cycle
void createCycle(node* &head,int a,int b) {
int cnta = 0,cntb = 0;
node* p1 = head;
node* p2 = head;
while(cnta != a || cntb != b) {
if(cnta != a) p1 = p1->next, ++cnta;
if(cntb != b) p2 = p2->next, ++cntb;
}
p2->next = p1;
}
//utility function to detect cycle
bool cycleDetect(node* head) {
unordered_set<node*> hashTable;
while(head != NULL) {
if(hashTable.find(head) != hashTable.end()) return true;
hashTable.insert(head);
head = head->next;
}
return false;
}
int main() {
node* head = NULL;
insertNode(head,1);
insertNode(head,2);
insertNode(head,3);
insertNode(head,4);
createCycle(head,1,3);//creating cycle in the list
if(cycleDetect(head) == true)
cout<<"Cycle detected\n";
else
cout<<"Cycle not detected\n";
return 0;
}
Output: Cycle detected
Time Complexity: O(N)
Reason: Entire list is iterated once.
Space Complexity: O(N)
Reason: All nodes present in the list are stored in a hash table.
Java Code
import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
//utility function to insert node in the list
class TUF{
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);
if(head == null) {
head = newNode;
return head;
}
Node temp = head;
while(temp.next != null) temp = temp.next;
temp.next = newNode;
return head;
}
//utility function to create cycle
static void createCycle(Node head,int a,int b) {
int cnta = 0,cntb = 0;
Node p1 = head;
Node p2 = head;
while(cnta != a || cntb != b) {
if(cnta != a)
{p1 = p1.next; ++cnta;}
if(cntb != b)
{p2 = p2.next; ++cntb;}
}
p2.next = p1;
}
//utility function to detect cycle
static boolean cycleDetect(Node head) {
HashSet <Node> hashTable=new HashSet<>();
while(head != null) {
if(hashTable.contains(head)) return true;
hashTable.add(head);
head = head.next;
}
return false;
}
public static void main(String args[]) {
Node head = null;
head=insertNode(head,1);
head=insertNode(head,2);
head=insertNode(head,3);
head=insertNode(head,4);
createCycle(head,1,3);//creating cycle in the list
if(cycleDetect(head) == true)
System.out.println("Cycle detected");
else
System.out.println("Cycle not detected");
}
}Output: Cycle detected
Time Complexity: O(N)
Reason: Entire list is iterated once.
Space Complexity: O(N)
Reason: All nodes present in the list are stored in a hash table.
Python Code
class Node:
def __init__(self, val):
self.val = val
self.next = None
# utility function to insert node at the end of the linked list
def insertNode(head, val):
newNode = Node(val)
if head == None:
head = newNode
return head
temp = head
while temp.next != None:
temp = temp.next
temp.next = newNode
return head
# utility function to create cycle
def createCycle(head, a, b):
cnta = 0
cntb = 0
p1 = head
p2 = head
while cnta != a or cntb != b:
if cnta != a:
p1 = p1.next
cnta += 1
if cntb != b:
p2 = p2.next
cntb += 1
p2.next = p1
# utility function to detect cycle
def cycleDetect(head):
hashTable = set()
while head != None:
if head in hashTable:
return True
hashTable.add(head)
head = head.next
return False
if __name__ == "__main__":
head = None
head = insertNode(head, 1)
head = insertNode(head, 2)
head = insertNode(head, 3)
head = insertNode(head, 4)
createCycle(head, 1, 3) # creating cycle in the list
if cycleDetect(head) == True:
print("Cycle detected")
else:
print("Cycle not detected")Output: Cycle detected
Time Complexity: O(N)
Reason: Entire list is iterated once.
Space Complexity: O(N)
Reason: All nodes present in the list are stored in a hash table.
Solution: Slow and Faster Pointer
Approach:
We will use two pointers with different steps forward. The process is as follows:-
- We will take two pointers, namely fast and slow. Fast pointer takes 2 steps ahead and slow pointer takes 2 points ahead.
- Iterate through the list until the fast pointer is equal to NULL. This is because NULL indicates that there is no cycle present in the given list.
- Cycle can be detected when fast and slow pointers collide.
Dry Run:
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
class node {
public:
int num;
node* next;
node(int val) {
num = val;
next = NULL;
}
};
//utility function to insert node in the list
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
head = newNode;
return;
}
node* temp = head;
while(temp->next != NULL) temp = temp->next;
temp->next = newNode;
return;
}
//utility function to create cycle
void createCycle(node* &head,int a,int b) {
int cnta = 0,cntb = 0;
node* p1 = head;
node* p2 = head;
while(cnta != a || cntb != b) {
if(cnta != a) p1 = p1->next, ++cnta;
if(cntb != b) p2 = p2->next, ++cntb;
}
p2->next = p1;
}
//utility function to detect cycle
bool cycleDetect(node* head) {
if(head == NULL) return false;
node* fast = head;
node* slow = head;
while(fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) return true;
}
return false;
}
int main() {
node* head = NULL;
insertNode(head,1);
insertNode(head,2);
insertNode(head,3);
insertNode(head,4);
createCycle(head,1,3);//creating cycle in the list
if(cycleDetect(head) == true)
cout<<"Cycle detected\n";
else
cout<<"Cycle not detected\n";
return 0;
}
Output: Cycle detected
Time Complexity: O(N)
Reason: In the worst case, all the nodes of the list are visited.
Space Complexity: O(1)
Reason: No extra data structure is used.
Java Code
import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
//utility function to insert node in the list
class TUF{
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);
if(head == null) {
head = newNode;
return head;
}
Node temp = head;
while(temp.next != null) temp = temp.next;
temp.next = newNode;
return head;
}
//utility function to create cycle
static void createCycle(Node head,int a,int b) {
int cnta = 0,cntb = 0;
Node p1 = head;
Node p2 = head;
while(cnta != a || cntb != b) {
if(cnta != a)
{p1 = p1.next; ++cnta;}
if(cntb != b)
{p2 = p2.next; ++cntb;}
}
p2.next = p1;
}
//utility function to detect cycle
static boolean cycleDetect(Node head) {
if(head == null) return false;
Node fast = head;
Node slow = head;
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
return false;
}
public static void main(String args[]) {
Node head = null;
head=insertNode(head,1);
head=insertNode(head,2);
head=insertNode(head,3);
head=insertNode(head,4);
createCycle(head,1,3);//creating cycle in the list
if(cycleDetect(head) == true)
System.out.println("Cycle detected");
else
System.out.println("Cycle not detected");
}
}Output: Cycle detected
Time Complexity: O(N)
Reason: In the worst case, all the nodes of the list are visited.
Space Complexity: O(1)
Reason: No extra data structure is used.
Python Code
class Node:
def __init__(self, val):
self.val = val
self.next = None
# utility function to insert node at the end of the linked list
def insertNode(head, val):
newNode = Node(val)
if head == None:
head = newNode
return head
temp = head
while temp.next != None:
temp = temp.next
temp.next = newNode
return head
# utility function to create cycle
def createCycle(head, a, b):
cnta = 0
cntb = 0
p1 = head
p2 = head
while cnta != a or cntb != b:
if cnta != a:
p1 = p1.next
cnta += 1
if cntb != b:
p2 = p2.next
cntb += 1
p2.next = p1
# utility function to detect cycle
def cycleDetect(head):
if head == None:
return False
fast = head
slow = head
while fast.next != None and fast.next.next != None:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
if __name__ == "__main__":
head = None
head = insertNode(head, 1)
head = insertNode(head, 2)
head = insertNode(head, 3)
head = insertNode(head, 4)
createCycle(head, 1, 3) # creating cycle in the list
if cycleDetect(head) == True:
print("Cycle detected")
else:
print("Cycle not detected")Output: Cycle detected
Time Complexity: O(N)
Reason: In the worst case, all the nodes of the list are visited.
Space Complexity: O(1)
Reason: No extra data structure is used.
Special thanks to Dewanshi Paul and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article