৭-৭ঃ Printing Singly Linked List in Reverse

এবার আমরা লিঙ্কড লিস্টকে রিভার্স প্রিন্ট করব।

প্রথমে আমরা সিংগলি লিঙ্কড লিস্ট কে রিকারশন দিয়ে প্রিন্ট করার চেষ্টা করি। আমাদের নরমাল প্রিন্ট ফাংশনটি ছিল এরকম।

void print_linked_list(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}

আমরা একটি নোড নিয়ে হেড থেকে প্রিন্ট করা শুরু করতাম। প্রতিবার নোডকে তার নেক্সট নোডে নিয়ে যেতাম। নোড যখন নালে চলে যেত তখন আমরা প্রিন্ট করা থামিয়ে দিতাম। এই সেইম প্রসেস আমরা এখন রিকারশন দিয়ে করব।

void print_recursion(Node *n)
{
    // base case
    if (n == NULL)   // শুরুতে বেস কেস লিখা হচ্ছে। নোড যখন নালে চলে যাচ্ছে তখন আমরা প্রিন্ট করা থামিয়ে দিচ্ছি।
        return;      // বেস কেস ট্রু হলে রিটার্ন করে দিচ্ছি। 
    cout << n->val << " ";       // নোডের ভেলু প্রিন্ট করছি। 
    print_recursion(n->next);    // নোডকে তার নেক্সট নোডে নিয়ে যাচ্ছি। 
}

কোডটি রান করলে দেখব লিঙ্কড লিস্ট এর প্রতিটি এলিমেন্ট প্রিন্ট হচ্ছে। এবার আসি আমাদের মেইন টার্গেট কিন্তু এটি ছিল না। আমাদের টার্গেট ছিল লিঙ্কড লিস্ট রিভার্স প্রিন্ট করা। এটি আমরা নরমালি while লুপ দিয়ে করতে পারব না। কারন সিংগলি লিঙ্কড লিস্টে পিছনের দিকে আসা যায় না। সোজা প্রিন্ট করার সময় আমরা যেমন একটি টেম্প নোড নিয়ে হেড থেকে টেল পর্যন্ত প্রিন্ট করেছি, রিভার্স প্রিন্ট এর সময় কিন্তু আমরা সেইমভাবে একটি টেম্প নোড নিয়ে টেল থেকে হেড পর্যন্ত প্রিন্ট করতে পারব না। কারন সিংগলি লিঙ্কড লিস্টে টেল থেকে হেডের দিকে আসা যায় না।

তো এটি আমরা খুব সহজে রিকারশন দিয়ে করে ফেলতে পারি। আমরা যখন রিকারশন দিয়ে সোজা প্রিন্ট করেছি তখন আমরা শুরুতে কাজ করেছি ( cout << n->val << " "; ) তারপর রিকারশন ফাংশন কল করেছি ( print_recursion(n->next); ) । জাস্ট এই দুটি লাইন যদি আমরা উল্টিয়ে দেই তাহলেই আসলে আমাদের রিকারশন দিয়ে রিভার্স প্রিন্ট করা হয়ে যাবে। আমরা আগে কল করে করে একদম শেষ অর্থাৎ টেল পর্যন্ত যাব তারপর প্রিন্ট করা শুরু করব।

void print_reverse(Node *n)
{
    // base case
    if (n == NULL)
        return;

    print_reverse(n->next);   // আগে কল করছি। 
    cout << n->val << " ";    // তারপর কাজ করছি। 
}

এবার আমরা সিমুলেশনটা দেখে নেইঃ

n এখন ১০ এ আছে। বেস কেস এর কন্ডিশন সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

এবার n ২০ এ আছে। বেস কেস এর কন্ডিশন এবারও সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

এবার n ৩০ এ আছে। বেস কেস এর কন্ডিশন এবারও সত্য হচ্ছে না তাই আবার রিকারশন কল হচ্ছে।

এবার n নালে আছে। বেস কেস এর কন্ডিশন সত্য হচ্ছে তাই এবার এই রিকারশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

এখানে এসে ৩০ প্রিন্ট হচ্ছে। তারপর এই ফাংশনের কাজ শেষ এবার এই ফাংশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

এই ফাংশনে n এর মান ২০। তাই ২০ প্রিন্ট হচ্ছে। তারপর এই ফাংশনের কাজ শেষ এবার এই ফাংশনটি যেখান থেকে কল হয়েছিল সেখানে রিটার্ন হচ্ছে।

এই ফাংশনে n এর মান ১০। তাই ১০ প্রিন্ট হচ্ছে। এভাবে পুরো লিঙ্কড লিস্টটি রিভার্স প্রিন্ট হয়ে গেল।

সম্পূর্ণ কোডঃ

#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_recursion(Node *n)
{
    // base case
    if (n == NULL)
        return;
    cout << n->val << " ";
    print_recursion(n->next);
}
void print_reverse(Node *n)
{
    // base case
    if (n == NULL)
        return;

    print_reverse(n->next);
    cout << n->val << " ";
}
int main()
{
    Node *head = new Node(10);
    Node *a = new Node(20);
    Node *b = new Node(30);
    Node *c = new Node(40);
    Node *d = new Node(50);
    head->next = a;
    a->next = b;
    b->next = c;
    c->next = d;

    print_recursion(head);
    cout << endl;
    print_reverse(head);
    return 0;
}

কোডটি রান করলে দেখব প্রথমে লিঙ্কড লিস্ট সোজা প্রিন্ট হচ্ছে এবং তারপর রিভার্স প্রিন্ট হচ্ছে।