C++ Program to Detect a Cycle in a Linked List

1. Introduction

A common problem in computer science is determining whether a linked list has a cycle. A cycle in a linked list means that visiting some nodes, starting from the head node will eventually lead back to a previously visited node. This post will guide you through a C++ solution to detect a cycle in a linked list.

2. Program Overview

The widely accepted approach to solving this problem is by using "Floyd's Cycle-Finding Algorithm", commonly known as the "Tortoise and the Hare" approach. The basic idea is to use two pointers, one moving slowly (tortoise) and another moving fast (hare). If there's a loop, the fast pointer will eventually catch up to the slow pointer.

3. Code Program

#include<iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

bool hasCycle(Node* head) {
    if(!head || !head->next) return false;

    Node* slow = head;
    Node* fast = head->next;
    while(slow != fast) {
        if(!fast || !fast->next) return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

int main() {
    Node* head = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
    Node* fourth = new Node(4);

    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = second;  // Creates a cycle

    if (hasCycle(head))
        cout << "Cycle detected in the linked list." << endl;
    else
        cout << "No cycle detected in the linked list." << endl;

    // To prevent a memory leak, you would typically free nodes before exiting.
    // But, for the purpose of this demonstration, we're focusing on cycle detection.
    return 0;
}

Output:

Cycle detected in the linked list.

4. Code Explanation

The Node class represents an element in our linked list. 

The function hasCycle checks for a cycle in the list using two pointers, slow and fast. As slow moves one step at a time and fast moves two steps, if there is a cycle, the fast pointer will eventually catch up to the slow pointer. If fast reaches the end of the list, then there's no cycle.

In our main function, we create a small linked list and introduce a cycle. The program then checks and correctly identifies that a cycle exists.

To avoid memory leaks in real-world applications, always remember to delete nodes and linked lists when they are no longer needed.

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

Explore My Udemy Courses View Developer Roadmaps

By Ramesh Fadatare - Udemy Instructor Partner