এই সমস্যায়, আমাদের একটি লিঙ্ক করা তালিকা দেওয়া হয়েছে যাতে লুপ থাকতে পারে। আমাদের কাজ হল লিঙ্ক করা তালিকায় লুপের দৈর্ঘ্য খুঁজে বের করা।
সমস্যা বর্ণনা: আমাদের লুপে নোডের সংখ্যা গণনা করতে হবে যদি এতে একটি লুপ থাকে অন্যথায় -1 ফেরত দেয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট: লিঙ্কড-লিস্ট :
আউটপুট: 8
সমাধান পদ্ধতি
সমস্যা সমাধানের জন্য, আমাদের প্রথমে লিঙ্ক করা তালিকায় একটি লুপ আছে কিনা তা পরীক্ষা করতে হবে। এটি পরীক্ষা করার একটি পদ্ধতি হল Floyd’s Cycle Finding Algorithm ব্যবহার করা।
ফ্লয়েডস সাইকেল ফাইন্ডিং অ্যালগরিদমে, আমরা দুটি পয়েন্টার ব্যবহার করে লিঙ্কযুক্ত তালিকাটি অতিক্রম করব। একটি স্লোপয়েন্টার যেটি 1 দ্বারা বৃদ্ধি পায় এবং আরেকটি হল fastPointer যেটি 2 দ্বারা বৃদ্ধি পায়। যদি উভয় সংখ্যা কোনো সময়ে মিলিত হয় তাহলে একটি লুপ আছে অন্যথায় নয়।
একটি লুপ বিদ্যমান থাকলে, আমাদের লুপে উপস্থিত নোডের সংখ্যা গণনা করতে হবে। এর জন্য আমরা সেই বিন্দু থেকে শুরু করব যেখানে slowPointer এবং fastPointer দেখা করুন এবং তারপরে অবস্থানে ফিরে যাওয়ার জন্য অতিক্রম করা নোডের সংখ্যা গণনা করুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
int countLoopNodespoint(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 countLoopNodespoint(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;
cout<<"The number of nodes in the loop are "<<countLoopNode(head);
return 0;
} আউটপুট
The number of nodes in the loop are 6>]
