इस समस्या में, हमें एक लिंक्ड लिस्ट दी गई है जिसमें लूप हो सकते हैं। हमारा कार्य लिंक्ड लिस्ट में लूप की लंबाई ढूंढना है।
समस्या विवरण: हमें लूप में नोड्स की संख्या गिननी है यदि इसमें लूप है अन्यथा -1 वापस करें।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट: linked-list :
आउटपुट: 8
समाधान दृष्टिकोण
समस्या को हल करने के लिए, हमें पहले जांचना होगा कि लिंक्ड लिस्ट में लूप है या नहीं। इसकी जांच करने का एक दृष्टिकोण फ्लॉयड के चक्र खोज एल्गोरिदम का उपयोग करना है।
फ्लॉयड के चक्र खोज एल्गोरिदम में, हम दो पॉइंटर्स का उपयोग करके लिंक्ड लिस्ट को ट्रैवर्स करेंगे। एक स्लो पॉइंटर जो 1 से बढ़ता है और दूसरा फास्ट पॉइंटर जो 2 से बढ़ता है। यदि दोनों किसी बिंदु पर मिलते हैं तो लूप मौजूद है अन्यथा नहीं।
यदि लूप मौजूद है, तो हमें लूप में मौजूद नोड्स की संख्या गिननी होगी। इसके लिए हम उस बिंदु से शुरू करेंगे जहां स्लो पॉइंटर और फास्ट पॉइंटर मिलते हैं और फिर उस स्थिति पर वापस आने के लिए ट्रैवर्स किए गए नोड्स की संख्या गिनेंगे।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#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
