Detect Cycle in a Linked List in C++.

Given the head of a linked list, detect if the given linked list contains a cycle. Return true if there exists a cycle else return false. Below is an example of two linked lists containing cycles.

Approach 1: Using Hashmap.

In this approach, you are going to insert all the nodes one by one inside a hashmap, and whenever you found a condition that a particular node is already present in the hashmap then it means there exists a cycle so return true.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using hashmap*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    unordered_set<ListNode*> hp;
    //loop to check cycle
    while(head != NULL){

        if(hp.find(head) != hp.end())
           return true;
        hp.insert(head);   
        head = head->next;   
    }
    return false;
}
int main(){

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes present.
• Space Complexity: O(n) because we are using one extra hashmap.

Approach 2: Two Pointer Approach (Slow and Fast Pointer).

In this approach, you need to use two pointers and one pointer will move slower than the other pointer. If the linked list contains a cycle then slow and fast pointers must meet at some point and if they meet each other at any point it means there exists a cycle.

• Initialize two pointers, slow and fast with the head of the linked list.
• Traverse the list, every time the slow pointer moves one step, and the faster moves two steps
• If there is a cycle then both slow and fast pointers will meet at some point, return true if they meet else return false.

C++ Solution Code:

/*C++ Program detect cycle in a linked list using 
two pointer approach*/
#include<bits/stdc++.h>
using namespace std;

class ListNode{
    public:
      int data;
      ListNode *next;

    //constructor
    ListNode(int data){
        this->data = data;
        this->next = NULL;
    }  
};
//creating new node
ListNode *newNode(int data){
    ListNode *temp = new ListNode(data);
    temp->next = NULL;
    return temp;
}
//function to print linked list
void printList(ListNode *head){
    ListNode *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}
//Function to detect cycle of linked list
bool detectCycle(ListNode *head){
    
    if(head == NULL) return false;

    ListNode* slow = head;
    ListNode* fast = head;

    while(fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast) return true; //cycle detected
    }
    return false;
}
int main(){

    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next = head; //cycle formation

    bool check = detectCycle(head);

    if(check)
      cout<<"Linked List contains a cycle.";
    else
      cout<<"Linked List does not contain a cycle.";

    return 0;
}

Output:

Linked List contains a cycle.

• Time Complexity: O(n) where n is the number of nodes in the linked list.
• Space Complexity: O(1)

Related Articles:

• Convert Binary Linked List to Integer.

• Find the Middle of the Singly Linked List in C++.

• Reverse a Singly Linked List in C++.

• Merge Two Sorted Linked List in C++.

• Intersection Point of Two Linked Lists in C++.