मान लें कि हमारे पास एक लिंक्ड सूची है, और हमें यह जांचना है कि कोई चक्र है या नहीं। दी गई लिंक्ड सूची में चक्र का प्रतिनिधित्व करने के लिए, हम पॉज़ नामक एक पूर्णांक सूचक का उपयोग करेंगे। यह स्थिति लिंक की गई सूची में एक स्थिति का प्रतिनिधित्व करती है जहां पूंछ जुड़ा हुआ है। तो अगर पॉज़ -1 है, तो लिंक की गई सूची में कोई चक्र मौजूद नहीं है। उदाहरण के लिए, लिंक की गई सूची [5, 3, 2, 0, 4, 7], और पॉज़ =1 की तरह है। तो एक चक्र है, और पूंछ दूसरे नोड से जुड़ी है। बाधा यह है कि हम सूची को संशोधित नहीं कर सकते हैं
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- धीमा:=सिर और तेज़:=सिर
- जबकि धीमा, तेज़ और अगला तेज़ उपलब्ध है, तब
- धीमी :=धीमी के आगे
- उपवास :=अगला (उपवास के बाद)
- अगर धीमा =तेज़ है, तो ब्रेक करें
- अगर उपवास खाली नहीं है या पहले का अगला खाली नहीं है, तो शून्य पर लौटें
- अगर धीमा =तेज, तो
- धीमा:=सिर
- जबकि धीमी गति तेज के समान नहीं है
- धीमा:=धीमी और तेज़ के बाद:=तेज़ के बाद
- धीमे वापसी
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
}
};
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 << "Tail is connected to the node with value:" <<ob.detectCycle(head)->val;
} इनपुट
[5,3,2,0,-4,7] 1
आउटपुट
Tail is connected to the node with value:3