মডিউল ১১-২ঃ Linked List Cycle

প্রবলেম লিংকঃ Linked List Cycle

প্রবলেম স্টেটমেন্টঃ একটি লিঙ্কড লিস্টের হেড নোড দেওয়া থাকবে। লিস্টে কোন সাইকেল আছে কিনা তা বলতে হবে। সল্যুশনঃ আমরা পূর্বের মডিউলে দেখা সাইকেল ডিটেকশন এর মতো করেই করে ফেলতে পারব। স্লো ফাস্ট দুইটা পয়েন্টার নিব। ফাস্ট পয়েন্টার লাস্টে চলে না যাওয়া পর্যন্ত আমরা চেক করব কোথাও স্লো এবং ফাস্ট সেইম হয়ে যাচ্ছ কিনা। যদি সেইম হয়ে যায় তাহলে সাইকেল আছে তাই ট্রু রিটার্ন করে দিব। আর যদি সেইম না থাকে তাহলে লুপ শেষে ফলস রিটার্ন করব।

class Solution
{
public:
    bool hasCycle(ListNode *head)
    {
        ListNode *slow = head;
        ListNode *fast = head; // স্লো ফাস্ট দুইটা পয়েন্টার নিব
        while (fast != NULL && fast->next != NULL)  // ফাস্ট পয়েন্টার লাস্টে চলে না যাওয়া পর্যন্ত লুপ চালাব
        {
            slow = slow->next;    // স্লো এক নোড করে সামনে আগাবে। 
            fast = fast->next->next;   // ফাস্ট দুই নোড করে সামনে আগাবে। 
            if (slow == fast)    // যদি স্লো এবং ফাস্ট সেইম হয়ে যায় তাহলে সাইকেল আছে তাই ট্রু রিটার্ন করে দিব
            {
                return true;
            }
        }
        return false;     // আর যদি সেইম না থাকে তাহলে লুপ শেষে ফলস রিটার্ন করব।
    }
};