১০-৭ঃ Reverse a Doubly Linked List

আমরা গত মডিউলে একটি Singly Linked List কে রিভার্স করা দেখেছি। এখন দেখবো কীভাবে একটি Doubly Linked List কে রিভার্স করা যায়। যেহেতু আমরা Doubly Linked List এর বাম থেকে ডানে , এবং ডান থেকে বামে দুই দিকে Traverse করতে পারি , তাই এই ক্ষেত্রে আমরা Two Pointer Approach এ চিন্তা করতে পারি। Two pointer Approach এর সাহায্যে কীভাবে একটি Array Reverse করতে হয় তা আমরা আগের মডিউল গুলাতে দেখেছি । Array এর ক্ষেত্রে আমরা দুটি পয়েন্টার i এবং j নিয়েছিলাম , i তে রেখেছিলাম array এর ০ তম index এবং j তে রেখেছিলাম array এর শেষ element বা n-1 তম index. এরপর আমরা ar[i] এবং ar[j] কে swap করতাম . swap করা শেষে i++ অর্থাৎ i কে এক ঘর সামনে নিয়ে যাবো , এবং j-- অর্থাৎ j কে এক ঘর পিছনে নিয়ে যাবো। এই প্রসেস চলতে থাকবে যতক্ষন i এর ভ্যালু j থেকে ছোট হবে. Doubly Linked List এর ক্ষেত্রেও আমরা ঠিক সেইম ভাবে কাজ টি করবো। ১। প্রথমে দুটি পয়েন্টার নিবো i এবং j পয়েন্টার নিবো. i কে পয়েন্ট করবো লিস্ট এর Head এ , এবং j কে পয়েন্ট করবো লিস্ট এর tail এ ২। এরপর i যে Node এ পয়েন্ট করা আছে ঐ Node এর ভ্যালু এবং j যে Node এ আছে ঐ Node এর ভ্যালু গুলা swap করবো

৩। swap করার পর , আমরা i পয়েন্টার কে এক ঘর ডানে নিয়ে যাবো অর্থাৎ i = i->next হয়ে যাবে এবং j পয়েন্টার কে এক ঘর বামে নিয়ে যাবো। অর্থাৎ j = j->prev এ নিয়ে যাবো

এই প্রসেস চলতে থাকবে যতক্ষন i!=j এবং i->next != j হবে । উপরের প্রসেসে Two Pointers approach বুঝতে আশা করি কারো অসুবিধা নেই। সাধারণত এই কন্ডিশনের লজিক টা বুঝতে অসুবিধা হয়। আসুন দেখে ছবির মাধ্যমে দেখে নেয়া যাক , কীভাবে এই কন্ডিশন এপ্লাই হচ্ছে। প্রথমে দেখে নেয়া যাক , বিজোড় সংখ্যক নোডের জন্য Stop condition টা কেমন হচ্ছে

এখানে দেখা যাচ্ছে i এবং j পয়েন্টার একটি Node এ এসে মিলিত হয়েছে , এরপর আর আমাদের কোনো swap অপারেশন করার প্রয়োজন নেই তার মানে i==j হলে আমরা লুপ টি ব্রেক করে দিবো। এরপর দেখে নেয়া যাক , যদি জোড় সংখ্যক Node থাকে তবে কী করা যায়

এখানে দেখা যাচ্ছে ৩য় iteration j বামে মুভ করেছে এবং i ডানে মুভ করেছে। যার কারণে আমাদের কাজ টি ঠিক মতো হবে না। অর্থাৎ এর j এবং i intersect করে move করার আগে তাদের থামাতে হবে। অর্থাৎ 2nd iteration এর সময় আমরা লুপ টি থামিয়ে দিবো। অর্থাৎ i এবং j যখন পাশাপাশি থাকবে অর্থাৎ i এর নেক্সট এ j থাকবে। i ->next !=j যতক্ষন হবেনা ততক্ষন আমরা লুপ চালাবো। পাশাপাশি হলে সেখানে থেমে যাবো।

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node *prev;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
        this->prev = NULL;
    }
};
void print_normal(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
void reverse(Node *head, Node *tail)
{
    Node *i = head; // i পয়েন্টারকে head এ পয়েন্ট করালাম
    Node *j = tail; // j পয়েন্টারকে tail এ পয়েন্ট করালাম
    while (i != j && i->next != j) // যতক্ষন পর্যন্ত condition True হচ্ছে ততক্ষন লুপ চালাবো
    {
        swap(i->val, j->val); // কারেন্ট i এবং j যে Node এ পয়েন্ট করা আছে ঐ Node গুলার ভ্যালু swap করলাম 
        i = i->next; // i কে একঘর ডানে মুভ করলাম 
        j = j->prev; // j কে একঘর বামে মুভ করলাম 
    }
    swap(i->val, j->val); // Node সংখ্যা জোড় হলে যেহেতু i->next = j কন্ডিশনে loop ব্রেক হবে তখন উপরের লুপে মাঝামাঝি দুটি Node এর ভ্যালু swap হবে না। এইক্ষেত্রে আমরা manually কাজটি করে নিলাম।  
}
int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node (30) ;
    Node *c = new Node(40) ; 
    Node *tail = c ;

    // connection
     head->next = a;
     a->prev = head;
     a->next = b;
     b->prev = a;
     b->next = c;
     c->prev = b;

    reverse(head, tail);
    print_normal(head); // 40 30 20 10 

    return 0;
}