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