১০-৫ , ১০-৬ঃ Reverse a Singly Linked List

এই মডিউলে আমরা জানবো কীভাবে একটি Singly Linked LIst কে Reverse করা যায়। প্রথমে দেখে নেয়া যাক একটি Reverse Singly Linked লিস্ট দেখতে কেমন হবে । প্রথমে চিন্তা করা যাক , আমাদের Reverse করার চিরচেনা উপায় Two Pointers এর সাহায্যে একটি Singly Linked List , Reverse করা যাবে কিনা। Two Pointers approach এর ক্ষেত্রে আমাদের একটি পয়েন্টার i রাখতে হয় প্রথম Node এ এবং j পয়েন্টার রাখতে হয় শেষ Node এ . এরপর এই দুটি element swap করতে হয় । swap করার পরে আমরা ডানের পয়েন্টার টি এক ঘর বামের দিকে / সামনের দিকের Node এ শিফট করি , এবং j পয়েন্টার টি এক ঘর বামের দিকে / পিছনের Node এ শিফট করি। যেহেতু Singly Linked List এ একটি Node হতে next পয়েন্টার এর সাহায্যে পরের Node এ যাওয়া যায় , এবং prev কোনো Node না থাকায় আগের Node এ যাওয়া যায় না , তাই আমরা i কে পরের Node এ shift করতে পারলেও j কে এর আগের Node এ shift করতে পারবো না। তাই , Singly Linked List এর Reversing এর ক্ষেত্রে Two Pointer Approach ব্যবহার করা যাবে না। এখন উপায় ? -> আগের মডিউল গুলোর Recursion এর সাহায্যে Singly Linked List Reverse প্রিন্ট এর ভিডিও তে আমরা দেখেছি , Recursion এর সাহায্যে আমরা Singly LInked List এ back থেকে Traverse করতে পারি। যদিও এটি Recursion এর কল গুলার কারণে Recursion call গুলো ব্যাক এ আসতে থাকা। কারণ আমাদের Recursion call এর timing এর উপর ভিত্তি করে Recursion call গুলো আগে , পরে activate হয়ে থাকে। আমরা যদি চাই , আমাদের Recursion call গুলা আগে হয়ে Singly Linked List এর একদম শেষের Node এ চলে যাক , এবং Call শেষ হবার পর Recursion call ব্যাক করার সময় operation করে আসুক , এই ক্ষেত্রে আমরা আগে Recursion কল করে দেয় , এবং পরবর্তীতে আমাদের অপারেশন ( যেমনঃ Reverse Print এর ক্ষেত্রে Printing Operation) তা আমরা করে থাকি। যেহেতু আমরা আপাতদৃষ্টিতে Singly Linked List এ ব্যাক এ আসার একটি উপায় পেয়ে গেছি , তাই এই মেথড এ আগানোর চেষ্টা করি। কিছু স্টেপ চিন্তা করি ।

• যেহেতু Head সবসময় কোনো List এর শুরুর Node এ পয়েন্ট করা থাকে , তাই Reverse করার সময় বর্তমান Linked List এর শেষের Node টি হবে Head Node. আমরা রিকারশন কল করতে করতে শেষের Node এ চলে আসবো , এবং সেই Node যদি শেষ Node হয় তবে , head কে এই Node এ পয়েন্ট করে আমরা Return করা শুরু করবো . এটি হবে আমাদের base case. সবুজ বক্স এর মাধ্যমে আমরা রিকারশন কল এর কোন Node এ আছি তা দেখছি।

• এরপর আমরা যদি দেখি বর্তমান Linked List এর B নোড টির নেক্সট পয়েন্টার C এর দিকে পয়েন্ট করা আছে , কিন্তু Reverse লিস্ট এর ক্ষেত্রে C এর next পয়েন্টার টি B এর দিকে পয়েন্ট করা আছে , অর্থাৎ উলটো। এখন আমরা C Node এ থাকা কালে কখনো B Node এর এড্রেস জানতে পারবো না। তাই C নোড এ থাকা কালে আমরা কোনো কাজ করতে পারবো না। কিন্তু যখন ই আমরা রিকারশন কল এর মাধ্যমে B নোড এ ব্যাক করবো , তখন ই একই সাথে B Node এবং C Node দুইটার ই এক্সেস আমাদের কাছে থাকবে। এরপর আমরা B এর নেক্সট Node ( b->next এর next পয়েন্টার অর্থাৎ B->next ->next পয়েন্টার Null থেকে চেঞ্জ করে B এর দিকে করে দিবো. এবং B এর next পয়েন্টার অর্থাৎ b->next কে Null এর দিকে পয়েন্ট করে দিবো।

• এরপর B Node এর কাজ শেষ করে A Node এ ফেরত আসবো। A Node এ আসার পর একই ভাবে আমরা A এবং B Node উভয় Node এর এক্সেস পাবো এরপর B Node ( A->next->next) এর নেক্সট পয়েন্টার A Node এর দিকে করে দিবো । এবং A এর next পয়েন্টার Null এর দিকে করে দিবো।

এইভাবে পুরো Singly Linked List টি Reverse হয়ে যায়। আশা করি , কন্সেপ্ট টি ঠিক মতো বুঝতে পেরেছেন , কনসেপ্ট বুঝে গেলে এখন আসুন , কোডে তা ছটফট Implement করে ফেলি।

Code :

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};

void print(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
void reverse(Node *&head, Node *cur) // cur নিয়েছি যাতে করে head চেঞ্জ না হয়ে যায়, এটি মূলত temp এর মতো কাজ করে
{
    if (cur->next == NULL) // base case 
    {
        head = cur; // যদি শেষ Node এ চলে আসি , তবে এটিকে head বলে দিচ্ছি 
        return; // এবং রিটার্ন করছি
    }
    reverse(head, cur->next); // আগে সব recursion call গুলা করে দিচ্ছি
   
   // কল শেষে কোনো একটি Node এ ব্যাক আসার পর
    cur->next->next = cur; // currently যে নোড এ আছি তার নেক্সট এর Node এর next পয়েন্টার চেঞ্জ করে নিজের দিকে করে দিচ্ছি
    cur->next = NULL; // এবং নিজের next পয়েন্টার Null এর দিকে করে দিচ্ছি
}
int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);

    head->next = a;
    a->next = b;
    b->next = c;
    reverse(head, head);
    print(head); 
    return 0;
}

Output : 40 30 20 10