Linked List Cycle - CPP Solution

1. Introduction

In this blog post, we address a classic problem in linked list manipulation: detecting if a linked list has a cycle. A cycle exists in a linked list if a node’s next pointer points to an earlier node in the list, leading to infinite traversal.

Problem

Given the head of a linked list, the task is to determine if the linked list has a cycle. The presence of a cycle is indicated if any node can be reached again by continuously following the next pointer.

2. Solution Steps

1. Use two pointers: slow and fast. Initially, both point to the head of the list.

2. Move slow by one step and fast by two steps in each iteration.

3. If there is a cycle, slow and fast will eventually meet; otherwise, fast will reach the end of the list.

4. Return true if slow and fast meet, indicating a cycle. Otherwise, return false.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to check if the linked list has a cycle
bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;

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

        if (slow == fast) {
            return true; // Cycle detected
        }
    }

    return false; // No cycle
}

int main() {
    // Creating a linked list with a cycle
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = head->next; // Creating a cycle

    bool result = hasCycle(head);
    cout << (result ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

Output:

Cycle detected

Explanation:

The hasCycle function employs the two-pointer technique, where slow moves one step at a time, and fast moves two steps. If there's a cycle, these pointers will meet at some point. If fast reaches the end of the list (i.e., encounters a nullptr), it means the list doesn't have a cycle. 

This approach efficiently detects the presence of a cycle without modifying the list structure.