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.