মডিউল ১১-১ঃ Middle of the Linked List

প্রবলেম লিংকঃ Middle of the Linked List

প্রবলেম স্টেটমেন্টঃ একটি লিঙ্কড লিস্ট দেওয়া থাকবে। তার মিডল এলিমেন্টটি রিটার্ন করতে হবে।

সল্যুশন-১ঃ আমরা প্রথমে লিঙ্কড লিস্ট এর সাইজ বের করে নিতে পারি। তারপর হেড থেকে সাইজ/২ পর্যন্ত লুপ চালিয়ে মিডল এলিমেন্টে চলে যেতে পারি। তারপর মিডল এলিমেন্টটি রিটার্ন করে দিলেই হয়ে যাবে।

class Solution
{
public:
    int size(ListNode *head)    // সাইজ বের করা হচ্ছে। 
    {
        ListNode *tmp = head;
        int cnt = 0;
        while (tmp != NULL)
        {
            cnt++;
            tmp = tmp->next;
        }
        return cnt;          // সাইজ রিটার্ন করা হচ্ছে।
    }
    ListNode *middleNode(ListNode *head)
    {
        int sz = size(head);     // শুরুতে সাইজ বের করে রাখা হচ্ছে। 
        ListNode *tmp = head;    // টেম্প নোড নিয়ে তাতে হেড নোডকে রাখা হচ্ছে। 
        for (int i = 1; i <= sz / 2; i++)   // তারপর লুপ চালিয়ে সাইজ/২ পর্যন্ত যাওয়া হচ্ছে।
        {
            tmp = tmp->next;
        }
        return tmp;        // লুপ শেষে টেম্প এখন সাইজ/২ অর্থাৎ মিডল এলিমেন্টে আছে। সেটি রিটার্ন করে দেওয়া হচ্ছে। 
    }
};

সল্যুশন-২ঃ আমরা গত মডিউলে দেখা স্লো ফাস্ট টেকনিক ব্যাবহার করেও এই প্রবলেমটি সল্ভ করতে পারি। আমরা জানি ফাস্ট পয়েন্টার দুই নোড করে সামনে আগায় এবং স্লো পয়েন্টার এক নোড করে সামনে আগায়। তাহলে যখন ফাস্ট পয়েন্টারটি লাস্ট নোডে থাকবে তখন অবশ্যই স্লো পয়েন্টারটি মিডল নোডে থাকবে। এই পদ্ধতিতে আমাদের আলাদা করে লিস্টের সাইজ বের করে নিতে হবে না।

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