আমাদের একটি লিঙ্ক তালিকা আছে বিবেচনা করুন, এবং আমাদের কোন চক্র আছে কি না তা পরীক্ষা করতে হবে। প্রদত্ত লিঙ্কযুক্ত তালিকায় চক্রের প্রতিনিধিত্ব করতে, আমরা pos নামক একটি পূর্ণসংখ্যা পয়েন্টার ব্যবহার করব। এই pos লিঙ্ক করা তালিকার একটি অবস্থানের প্রতিনিধিত্ব করে যেখানে লেজ সংযুক্ত থাকে। তাই যদি pos হয় -1, তাহলে লিঙ্ক করা তালিকায় কোন চক্র উপস্থিত নেই। উদাহরণস্বরূপ, লিঙ্ক করা তালিকাটি হল [5, 3, 2, 0, -4, 7], এবং pos =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
