Table of Contents
Problem Statement
“Linked List Cycle” problem states that you are given a linked list. Find if it contains any loop or not?
Linked list with cycle
Example
1->2->3
No Loop
Explanation: The linked list does not contain any loop because if it did then there would’ve been two no des pointing to the same node. Or there would not have been any node having Null as its next node.
1->2->3->4 ^ | |_____|
Yes there exists a loop
Explanation: Yes there is a loop because node having value 1 and node with value 4 is pointing to the same node 2.
Using Hashing Method
Algorithm
1. Initialize a hash table of type Node. 2. Start traversing the list. While node of the list is not null check if the current value is already stored in the hash table, if yes return true. 3. Else store it in the hash table and increment the pointer of the hash table. 4. Return false.
We are here using a hash table or HashSet to find if there exists a loop in the linked list. The same technique is used when we need to find if our array contains duplicates. We use HashSet to store the value which we want should not be repeated. Because a HashSet allows storing only a single instance of any element(i.e. it does not allow to store duplicates). This functionality suits our use case. Thus we use a HashSet to check while traversing the linked list if we find the same node twice. we know that there exists a loop in the linked list. But if we can traverse the linked list without finding the same node twice. we know that none of the elements has been repeated and there is no loop in the linked list.
Code
C++ Program to find Linked list cycle
#include <bits/stdc++.h>
using namespace std;
struct Node{
int data;
struct Node* next;
};
void push(struct Node** head_ref, int new_data){
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
bool detectCycle(struct Node* h){
unordered_set<Node*> s;
while (h != NULL) {
if (s.find(h) != s.end())
return true;
s.insert(h);
h = h->next;
}
return false;
}
int main(){
struct Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
head->next->next->next->next = head;
if(detectCycle(head))
cout << "Loop found";
else
cout << "No Loop";
return 0;
}Loop found
Java Program to find Linked list cycle
import java.util.*;
class Cycle{
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
static public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
static boolean detectCycle(Node h){
HashSet<Node> s = new HashSet<Node>();
while(h != null){
if(s.contains(h))
return true;
s.add(h);
h = h.next;
}
return false;
}
public static void main(String[] args){
Cycle list = new Cycle();
list.push(20);
list.push(4);
list.push(15);
list.push(10);
list.head.next.next.next.next = list.head;
if(detectCycle(head))
System.out.println("Loop found");
else
System.out.println("No Loop");
}
}Loop found
Complexity Analysis
Time Complexity
O(N) where n is the number of inserted nodes in the given list. Since we have used HashSet or unordered_set which ensures insertion and searching in O(1) which allowed us to achieve linear time complexity.
Space Complexity
O(N) because we used a HashSet wherein the worst case we’ll have to insert N nodes.
Floyd’s Cycle-Finding Algorithm
Steps
- Use two pointers slow and fast.
- Move slow pointer by 1 node and fast at 2 at each step.
- If both the pointers meet at any point, then the cycle is present.
Algorithm
1. Initialize two pointers fast and slow as head of the list. 2. Traverse while fast or slow is not null. Increment slow by 1 node and fast by 2 nodes. 3. Check at each traversal if slow equals to fast, print "Loop found" and return 1. 4. Else return 0 and print "No loop".
Code
C++ Program to find Linked list cycle
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node* next;
};
void push(Node** head_ref, int new_data){
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int detectCycle(Node* list){
Node *slow = list, *fast = list;
while (slow && fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
cout << "Found Loop";
return 1;
}
}
return 0;
}
int main(){
Node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 10);
head->next->next->next->next = head;
if(!detectCycle(head))
cout<<"No Loop";
return 0;
}
Loop found
Java Program to find Linked list cycle
class Cycle{
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public void push(int new_data){
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
int detectCycle(){
Node slow = head, fast = head;
while (slow != null && fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
System.out.println("Found loop");
return 1;
}
}
return 0;
}
public static void main(String args[]){
Cycle list = new Cycle();
list.push(20);
list.push(4);
list.push(15);
list.push(10);
list.head.next.next.next.next = list.head;
if(list.detectCycle()==0)
System.out.println("No loop");
}
}Loop found
Complexity Analysis
Time Complexity
O(N) where N is the number of inserted nodes in the given list.
Space Complexity
O(1) because we used constant extra space. here we had not stored any extra information regarding each of the nodes. Thus we have constant space complexity.
Marking visited nodes without modifying the linked list data structure
Algorithm to detect linked list cycle
1. Initialize an extra node. 2. Traverse through the list while the head is not null. If head->next is null i.e. there is no cycle, return false. 3. Else if head->next is equal to the extra node, return true. 4. Create a node to store the pointer of the next node. 5. Store extra node in a pointer to the next node. 6. Update the head to the next node. 7. Return false.
Here we created a temporary node, we point all the nodes to this new node. So, if at a time we come across a node that already points the temporary node. Then we know that there exists a loop else the linked list does not contain a cycle.
Code
C++ Program to find Linked list cycle
#include <iostream>
using namespace std;
struct Node{
int key;
struct Node* next;
};
Node* newNode(int key){
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
bool detectCycle(Node* head){
Node* temp = new Node;
while (head != NULL) {
if(head->next == NULL){
return false;
}
if(head->next == temp){
return true;
}
Node* nex = head->next;
head->next = temp;
head = nex;
}
return false;
}
int main(){
Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
head->next->next->next->next->next = head->next->next;
bool found = detectCycle(head);
if(found)
cout << "Loop Found";
else
cout << "No Loop";
return 0;
}Loop found
Java Program to find Linked list cycle
class Cycle{
static class Node {
int key;
Node next;
};
static Node newNode(int key){
Node temp = new Node();
temp.key = key;
temp.next = null;
return temp;
}
static void printList(Node head){
while (head != null) {
System.out.print(head.key + " ");
head = head.next;
}
System.out.println();
}
static boolean detectCycle(Node head){
Node temp = new Node();
while (head != null) {
if(head.next == null){
return false;
}
if (head.next == temp) {
return true;
}
Node nex = head.next;
head.next = temp;
head = nex;
}
return false;
}
public static void main(String args[]){
Node head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);
head.next.next.next.next.next = head.next.next;
boolean found = detectCycle(head);
if (found)
System.out.println("Loop Found");
else
System.out.println("No Loop");
}
}Loop found
Complexity Analysis
Time Complexity
O(N) where N is the number of inserted nodes in the given list.
Space Complexity
O(1) because we used constant extra space. Here we had created just a single new node to which all other nodes point.