মডিউল ১১-৪ঃ Reverse Linked List

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

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

class Solution
{
public:
    void reverse(ListNode *&head, ListNode *cur)  // সিংগলি লিঙ্কড লিস্ট রিভার্স করছি রিকারশন ব্যাবহার করে
    {
        if (cur->next == NULL)
        {
            head = cur;
            return;
        }
        reverse(head, cur->next);
        cur->next->next = cur;
        cur->next = NULL;
    }
    ListNode *reverseList(ListNode *head)
    {
        if (head == NULL)      // যদি লিঙ্কড লিস্টটি শুরুতেই ফাঁকা থাকে হেড নাল থাকে।
            return head;       // তাহলে আমরা ডিরেক্টলি হেড রিটার্ন করে দিব। 
        reverse(head, head);   // রিকারশন ফাংশন কল করা হচ্ছে। 
        return head;           // রিকারশন কল করা শেষে লিঙ্কড লিস্ট উল্টিয়ে যাবে। তখন হেড রিটার্ন করা হচ্ছে।  
    }
};