मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, और हमें जांचना है कि इसमें कोई साइकिल (चक्र) है या नहीं। दी गई लिंक्ड लिस्ट में साइकिल को दर्शाने के लिए, हम एक पूर्णांक पॉइंटर pos का उपयोग करेंगे। यह pos लिंक्ड लिस्ट में एक स्थिति दर्शाता है जहां टेल (tail) जुड़ा हुआ है। यदि pos -1 है, तो लिंक्ड लिस्ट में कोई साइकिल नहीं है। उदाहरण के लिए, लिंक्ड लिस्ट [5, 3, 2, 0, -4, 7] है, और pos = 1। तो एक साइकिल मौजूद है, और टेल दूसरे नोड से जुड़ा है। शर्त यह है कि हम लिस्ट को संशोधित नहीं कर सकते।
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- slow := head और fast := head
- जब तक slow, fast और fast का next उपलब्ध है:
- slow := slow का next
- fast := fast के next का next
- यदि slow = fast, तो ब्रेक करें
- यदि fast खाली नहीं है या fast का next खाली नहीं है, तो null वापस करें
- यदि slow = fast, तो:
- slow := head
- जब तक slow, fast के समान नहीं है:
- slow := slow का next और fast := fast का next
- slow वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i < v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
ListNode *get_node(ListNode *head, int pos){
ListNode *ptr = head;
if(pos != -1){
int p = 0;
while(p < pos){
ptr = ptr->next;
p++;
}
return ptr;
}
return NULL;
}
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(slow && fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(slow == fast) break;
}
if(!fast || !fast->next) return NULL;
if(slow == fast){
slow = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
}
return slow;
}
};
int main(){
Solution ob;
vector<int> v = {5,3,2,0,-4,7};
ListNode *head = make_list(v);
int pos = 1;
ListNode *lastNode = get_node(head, v.size() - 1);
lastNode->next = get_node(head, pos);
cout << "टेल इस नोड से जुड़ा है जिसका मान: " << ob.detectCycle(head)->val;
}
इनपुट
[5,3,2,0,-4,7] 1
आउटपुट
टेल इस नोड से जुड़ा है जिसका मान: 3