1=>2=>3=>4=>5=>6=>null

1=>2=>3=>4

↑ ↓

6 <= 5

উপরের দুটি লিংক লিস্টের দিকে তাকাও, প্রথম টিতে কোনো cycle নেই কারন, যেহেতু সর্বশেষ node এর পরে null. কিন্তু দ্বিতীয় link list টিতে cycle রয়েছে যেহেতু শেষ node 6 এর পরে তা null না হয়ে সেটি আবার node 2 এ point করছে। অর্থাত এখানে 2,3,4,5,6 node মিলে একটি cycle create করেছে।

আর আমাদের এটাই check করতে হবে।

𝗧𝗵𝗲𝗼𝗿𝘆:

সরাসরি Code এ যাওয়ার আগে তোমাদের ছোট্ট করে একটা analogy দিতে চাই, যাতে পরবর্তিতে logic বুঝতে সুবিধা হয়।

একটি বৃত্তাকার মাঠ কল্পনা করো।তুমি ও তোমার বন্ধু রাশেদ এই বৃত্তাকার মাঠের পরিধি বারাবর দৌড় প্রতিযোগীতা করতে চাচ্ছ । এখন মনে কর তোমার বন্ধু রাশেদ যত জোরে দৌড়াতে পারে তুমি তার চাইতে দ্বীগুন গতিতে দৌড়াতে পারো। রাশেদ একধাপ গেলে তুমি দুই ধাপ যাও। রাশেদ 10km বেগে দৌড়ালে তুমি দৌড়াও 20km বেগে, অনেকটা এরকম।

এখন মাঠ যেহেতু গোলাকার,দৌড় শুরু করা পর তুমি প্রথমেই রাশেদকে ছাড়িয়ে আগে চলে যাবে। দৌড় যদি চলমান থাকে তাহলে পরবর্তিতে তুমি আবার রাশেদকে ধরে ফেলতে পারবে। অর্থাত তুমি আর রাশেদ একই জায়গায় মিলিত হবে।এভাবে দৌড় চলমান থাকলে কিছু সময় পরপর তুমি বারবার তোমার বন্ধু রাশেদের সাথে একই জায়গায় মিলিত হতেই থাকবে।

এবারে, আরেকটা জিনিস চিন্তা করো,মনে কর আবারও তোমরা দৌড় প্রতিযোগীতা করবে। কিন্তু এবার তোমরা আর কোন গোলাকার মাঠ নয় বরং একটি সোজা সরলরৈখিক মাঠ বরাবর দৌড়াবে। এবারে, দৌড় শুরু করার কয়েক মুহূর্তেই তুমি তোমার বন্ধু রাশেদকে ছাড়িয়ে গেলে। কিন্তু বলোতো তুমি কি এখন তোমার বন্ধুর সাথে মাঠের অন্য কোনো জায়গায় আবার মিলিত হবে? অবশ্যই না। কারন এবারেরে মাঠ তো বৃত্তাকার নয়, এটি সোজা মাঠ। তাই যত জোরেই দৌড়াও না কেনো তুমি রাশেদের সাথে আর কোথাও মিলিত হবে না।

এখন এই কন্সেপ্ট কাজে লাগিয়ে তুমি লিংক লিস্টে সাইকেল আছে কিনা তা নির্ণয় করতে পারো।

চলো,এখন আমরা ধাপে ধাপে আমাদের code developed করবো।

𝗖𝗼𝗱𝗲:

প্রথমেই fast এবং slow নামক দুইটি Node type pointer নিয়ে নেই। নাম শুনেই বুঝতে পারছো, fast নামক pointer টি হলে তুমি, যে দ্বিগুন গতিতে চলবে। আর slow নামক pointer টি হলো তোমার বন্ধু রাশেদ যে তোমার অর্ধেক গতিতে চলবে।

Node *fast=head;

Node *slow=head;

লক্ষ কর, এখানে slow ও fast উভয়েই head থেকে শুরু হবে,যেহেতু starting line সবার ক্ষেত্রে same.

এবার একটা loop এর মাধ্যমে slow এবং fast কে আগানো শুরু করি। slow যদি এক ঘর যায় তাহলে fast যাবে দুই ঘর।

slow=slow->next;

fast=fast->next->next;

এভাবে চলতে চলতে,যদি দেখি slow এবং fast কোনো এক জায়গায় মিলিত হয়েছে, তাহলে বুঝবো cycle বিদ্যমান আছে(বৃত্তাকার মাঠ)। আর তা না হলে fast যেহেতু বেশি গতিতে যাচ্ছে,তাই fast সবার আগে finish line এ পৌছাবে, মানে null হবে, সেক্ষেত্রে cycle নাই (সোজা মাঠ)।

আমরা simple while loop দিয়ে এই কাজ চালাতে পারি।

তাহলে code দ্বারালো এমন:

void function()

{

bool ans=false;

Node *fast=head;

Node *slow=head;

while(fast!=NULL && fast->next!=NULL)

{

slow=slow->next; //একবার করে আগাবে।

fast=fast->next->next;//দুইবার করে আগাবে।

if(fast==slow)

{

ans= true;

break;

}

}

cout<<ans;

}

𝗖𝗼𝗱𝗲 𝗔𝗻𝗮𝗹𝗼𝗴𝘆:

চলো এখন code টা বিশ্লেষন করি:

প্রথমেই ans নামক একটি boolean variable নেয়া হয়েছে যেটি বর্তমানে false. ans যদি শেষ পর্যন্ত false ই থাকে তাহলে বুঝতে হবে cycle নাই, আর true হলে বুঝতে হবে cycle আছে।

এখন একটা একটা confusion দূর করি। তোমাদের মনে এরকম প্রশ্ন আসতেই পারে যে, while(fast!=NULL) এতটুকু condition দিলেই তো হতো । তার সাথে fast->next!=NULL এই condition যোগ করার কারন কী? একটু মাথা খাটালেই বুঝতে পারবে যে, fast যেহেতু দুইঘর করে আগাচ্ছে, সুতরাং কোনো সময় যদি তা link list এর শেষের node=6 এ চলে আসে,

( NULL এর আগের node) তাহলে এর পরের iteration এ fast=NULL না হওয়ার কারনে তা loop ভিতরে ঢুকবে ঠিকই, কিন্তু এখন fast কে দুইবার update করতে চাইবে। কিন্তু fast তো একবার update হয়েই NULL হয়ে যাবে। এবং পরবর্তীতে আর update হবেনা।

(NULL->next বলতে কিছু নেই) ।

এক্ষেত্রে আমরা null pointer exception বা segmentation fault এর মত error খাবো। তাই আমাদের সবসময় মাথায় রাখতে হবে যে fast NULL না হওয়ার পাশাপাশি যাতে fast এর পরে সর্বনিম্ন একটি valid node থাকে। তাই আমাদের এই extra আরেকটি condition দেওয়া। আশা করি এখন code বুঝতে আর কোনো সমস্যা হবে না।

চলো আমরা এবার আমাদের code কে একটু হাতে কলমে বিশ্লেষন করে দেখি সব ঠিকঠাক আছে কিনা।

প্রথম 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁 :

1=>2=>3=>4=>5=>6=>null

S

F

1’st iteration:

slow=1,fast=1এবং fast->next=2;

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=2;

fast=fast->next->next=3;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

2nd iteration:

1=>2=>3=>4=>5=>6=>null

S F

slow=2,fast=3 এবং fast->next=4;

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=3;

fast=fast->next->next=5;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

3rd iteration:

1=>2=>3=>4=>5=>6=>null

S F

slow=3,fast=5 এবং fast->next=6;

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=4;

fast=fast->next->next=NULL;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

4th iteration:

1=>2=>3=>4=>5=>6=>null

S F

slow=4,fast=NULL

এখন fast pointer টি NULL হয়ে গেছে,তাই loop এর condition মিথ্যা হবে এবং loop থেমে যাবে।

ans=false ই থেকে যাবে। এভাবে বুঝবো যে link list কোনো cycle নেই।

দ্বিতীয় 𝗟𝗶𝗻𝗸𝗲𝗱 𝗟𝗶𝘀𝘁 :

1st iteration:

F

S

1=>2=>3=>4

↑ ↓

6 <= 5

slow=1,fast=1 এবং fast->next=2

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=2;

fast=fast->next->next=3;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

2nd iteration:

S F

1=>2=>3=>4

↑ ↓

6 <= 5

slow=2,fast=3 এবং fast->next=4

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=3;

fast=fast->next->next=5;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

3rd iteration:

S

1=>2=>3=>4

↑ ↓

6 <= 5

F

slow=3,fast=5 এবং fast->next=6

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=4;

fast=fast->next->next=2;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

4th iteration:

F S

1=>2=>3=>4

↑ ↓

6 <= 5

slow=4,fast=2 এবং fast->next=3

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=5;

fast=fast->next->next=4;

slow এবং fast সমান নয় অতএব,পরবর্তী iteration এ যাও।

5th iteration:

F

1=>2=>3=>4

↑ ↓

6 <= 5

S

slow=5,fast=4 এবং fast->next=5

loop এর condition সত্য হবে।

অতএব slow এবং fast update হবে।

slow=slow->next=6;

fast=fast->next->next=6;

এখন slow এবং fast সমান হয়ে গেছে তাই,

if(slow==fast) এই condition ও সত্য হয়ে যাবে। এবং ans=true করে দিয়ে loop closed হয়ে যাবে।

অতএব linked list এ cycle বিদ্যমান!!

আশা করি এখন তুমি সহজেই linked list এ cycle detect করতে পারবে।