C++-এ লিংকড লিস্টে লুপের দৈর্ঘ্য বের করুন

একটি লিংকড লিস্ট দেওয়া আছে যেটিতে লুপ (সাইকেল) থাকতে পারে। লুপ থাকলে তার দৈর্ঘ্য (নোড সংখ্যা) বের করুন, নাইলে ০ বা -১ রিটার্ন করুন।

উদাহরণ

লিস্ট: ১→২→৩→৪→৫→৬→৭→(২-এ ফিরে যায়)

লুপের নোড: ২,৩,৪,৫,৬,৭ → দৈর্ঘ্য 6

অ্যালগরিদম: ফ্লয়েডস সাইকেল ফাইন্ডিং (টোয়েটার-হেয়ার)

1. দুই পয়েন্টার: slow (১ ধাপ), fast (২ ধাপ)।
2. যদি মিলে যান → লুপ আছে।
3. মিলন পয়েন্ট থেকে এক পয়েন্টার রেখে অন্যটি একধাপে ঘুরিয়ে কাউন্ট করুন যতক্ষণে আবার মিলে।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

int countLoopNodes(struct Node* n) {
    int res = 1;
    struct Node* temp = n;
    while (temp->next != n) {
        res++;
        temp = temp->next;
    }
    return res;
}

int countLoopNode(struct Node* list) {
    struct Node *slowPtr = list, *fastPtr = list;
    while (slowPtr && fastPtr && fastPtr->next) {
        slowPtr = slowPtr->next;
        fastPtr = fastPtr->next->next;
        if (slowPtr == fastPtr)
            return countLoopNodes(slowPtr);
    }
    return 0;
}

struct Node* newNode(int key) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = key;
    temp->next = NULL;
    return temp;
}

int main() {
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next->next = newNode(7);
    head->next->next->next->next->next->next->next = head->next; // Loop at node 2
    cout << "The number of nodes in the loop are " << countLoopNode(head);
    return 0;
}

আউটপুট

The number of nodes in the loop are 6

ব্যাখ্যা

• ফেজ ১ (ডিটেকশন): slow/fast পয়েন্টার মিললে লুপ কনফার্মড।
• ফেজ ২ (কাউন্টিং): মিলন পয়েন্ট থেকে একটা পয়েন্টার ঘুরিয়ে কাউন্ট।
• টাইম: O(n), স্পেস: O(1)।
• লুপ না থাকলে fastPtr বা fastPtr->next NULL হয়ে লুপ টার্মিনেট।

লুপের শুরুর নোড খুঁজতে (বোনাস)

Node* findLoopStart(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (!fast || !fast->next) return NULL;
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // লুপের শুরু
}