একটি লিংকড লিস্ট দেওয়া আছে, সেটিতে সাইকেল (cycle) আছে কিনা চেক করতে হবে। সাইকেল রিপ্রেজেন্ট করতে একটি পজিশন পয়েন্টার (pos) ব্যবহার করা হয়। pos = -1 হলে কোনো সাইকেল নেই। উদাহরণস্বরূপ, লিস্ট [5,3,2,0,-4,7] এবং pos = 1 হলে টেইল দ্বিতীয় নোডের সাথে কানেক্টেড। লিস্ট মডিফাই করা যাবে না।
সমাধান (ফ্লয়েডের সাইকেল ফাইন্ডিং অ্যালগরিদম):
- slow := head এবং fast := head
- while slow, fast এবং fast->next আছে
- slow := slow->next
- fast := fast->next->next
- যদি slow = fast, তবে ব্রেক
- যদি fast বা fast->next নেই, তবে NULL রিটার্ন
- যদি slow = fast
- slow := head
- while 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; inext != 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
