১০-৮ঃ Detect Cycle in Singly Linked List

এই মডিউলে আমরা একটি Singly Linked List এ কীভাবে Cycle Detect করতে হয় । প্রথমে জেনে নেয়া যাক Cycle বলতে কি বুঝানো হয়েছে। ধরুন আপনার এলাকায় তিনটি ঘর আছে যারা নিজেদের মধ্যে রাস্তা দিয়ে একজন আরেকজনের সাথে যুক্ত আছে নিচের ছবির মতো

এখন আমরা যদি A ঘর থেকে সোজা রাস্তা ধরে যাত্রা শুরু করি তবে B ঘরে যাবো , B ঘর থেকে যাবো C ঘরে , এবং C ঘর থেকে যাবো A ঘরে। অর্থাৎ যে ঘর (A) থেকে যাত্রা শুরু করেছিলাম আবার যাত্রা শেষ করে সেই ঘরেই ফিরে এসেছি। এইখানে রাস্তা গুলো এই ঘর গুলোর মধ্যে একটি সাইকেল বা লুপ তৈরি করেছে । এটিকে বলা হয় Cycle. এখন দেখে নেয়া যাক একটি Singly Linked List এ সাইকেল থাকলে তা দেখতে কেমন হবে ।

এখানে যদি আমরা Y Node হতে next , নেক্সট করে সামনে যেতে থাকি তবে যেহেতু আপাত দৃষ্টিতে Last Node হলো C . এবং C Node এর নেক্সট এ গেলে আমরা আবার Y Node এ ফিরে আসবো। অর্থাৎ এখানে একটি Cycle ক্রিয়েট হয়েছে. Singly Linked List এ Cycle Detect করার জন্য আমরা একটি নতুন টেকনিক শিখবো । যাকে বলা হয় Hare and Tortoise বা Slow and Fast টেকনিক। আগে দেখে নেয়া যাক এই টেকনিক কীভাবে Implement করতে হয়। ১। শুরুতে আমরা Two Pointers টেকনিক এর মতো দুটি পয়েন্টার নিবো যার নাম হবে Hare , Tortoise. যা Initially Singly Linked List এর প্রথম Node এ থাকবে। ২। এরপর Hare (fast) পয়েন্টার কে ২ ঘর করে করে সামনে নিতে থাকবো , এবং Tortoise (slow) পয়েন্টার কে একঘর একঘর সামনে নিতে থাকবো। ৩। দুটি পয়েন্টার যদি কোনো একটি মোমেন্ট এ একই জায়গায় মিলিত হয় তবে সেক্ষেত্রে আমরা বলতে পারবো , LInked List এ একটি Cycle রয়েছে। যদি মিলিত না হয় তবে সেই ক্ষেত্রে বলা যাবে , উক্ত Linked List এ কোনো Cycle নাই। আসেন কোড এর মাধ্যমে Implementation টা দেখি। Code :

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};
int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);

    head->next = a;
    a->next = b;

    Node *slow = head; // slow পয়েন্টার টি head এ পয়েন্ট করেছি 
    Node *fast = head; // fast পয়েন্টার টি head এ পয়েন্ট করেছি 
    bool flag = false; // Cycle পেয়েছি কিনা চেক করার জন্য flag রাখছি 
    while (fast != NULL && fast->next != NULL) // fast এবং fast->next যতক্ষন না হচ্ছে ততক্ষন লুপ চালাচ্ছি
    {
        slow = slow->next; // slow পয়েন্টার কে এক ঘর সামনে নিয়ে যাচ্ছি
        fast = fast->next->next; // fast পয়েন্টার কে দুই ঘর সামনে নিয়ে যাচ্ছি 
        if (fast == slow) // যদি কোনো Moment এ fast এবং slow পয়েন্টার same node এ পয়েন্ট করা থাকে 
        {
            flag = true; // তবে Cycle Detect হয়েছে এবং flag এর মান True করে দিলাম 
            break;
        }
    }
    if (flag == true) // flag এর মান true হলে Cycle পাওয়া গেছে 
        cout << "Cycle Detected" << endl;
    else
        cout << "No Cycle" << endl; // else কোনো cycle নেই
    return 0;
}