এই আর্টিকেলে, আমাদের একটি সিংলি লিংকড লিস্টের লিংকগুলো রিভার্স করতে হবে। আমাদের কাজ হল একটি ফাংশন তৈরি করা যা দেয়া সিংলি লিংকড লিস্টকে রিভার্স করতে সক্ষম। উদাহরণস্বরূপ
ইনপুট: লিংকড লিস্ট: 1→2→3→4→NULL আউটপুট: আমাদের ফাংশন প্রসেস করার পর: 4→3→2→1→NULL
সমাধানের পদ্ধতি
লিংকড লিস্ট রিভার্স করার বিভিন্ন পদ্ধতি আছে। সাধারণত আমাদের মনে একটা সহজ পদ্ধতি আসে: লিস্ট ট্রাভার্স করে যেতে হয় এবং ট্রাভার্স করার সময় সেটি রিভার্স করতে হয়।
সহজ পদ্ধতি
এই পদ্ধতিতে, আমরা লিংকড লিস্টে যাব এবং ট্রাভার্স করার সময় সেটি রিভার্স করার চেষ্টা করব।
উদাহরণ প্রোগ্রাম
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// লিংকড লিস্ট প্রিন্ট করার ফাংশন
void reverse() {
auto curr = head; // কারেন্ট পয়েন্টার
Node* prev = NULL; // প্রিভিয়াস পয়েন্টার
while (curr) {
auto temp = curr->next;
curr->next = prev;
prev = curr;
head = prev;
curr = temp;
}
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}
আউটপুট
85 15 4 20 20 4 15 85
এই পদ্ধতিতে, আমরা সিম্পলি লিস্ট ট্রাভার্স করছি এবং ট্রাভার্স করার সময় রিভার্স করছি। এটি একটি ভালো পদ্ধতি কারণ টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের লিস্টের আকার।
এখন আমরা এক্সপেরিমেন্ট করব যেখানে আমরা স্ট্যাক ব্যবহার করে লিস্ট রিভার্স করার চেষ্টা করব।
স্ট্যাক ব্যবহার করে পদ্ধতি
এই প্রোগ্রামে আমরা একটি স্ট্যাক ব্যবহার করব সব নোড সংরক্ষণ করার জন্য এবং স্ট্যাক থেকে পপ করে লিস্ট রিভার্স করব।
উদাহরণ প্রোগ্রাম
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// লিংকড লিস্ট প্রিন্ট করার ফাংশন
void reverse() {
auto curr = head; // কারেন্ট পয়েন্টার
Node* prev = NULL; // প্রিভিয়াস পয়েন্টার
stack<Node*> s;
while (curr) {
s.push(curr);
curr = curr->next;
}
prev = s.top();
head = prev;
s.pop();
while (!s.empty()) {
auto temp = s.top();
s.pop();
prev->next = temp;
prev = temp;
}
prev->next = NULL;
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}
আউটপুট
85 15 4 20 20 4 15 85
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা লিস্টের নোডগুলো ট্রাভার্স করার সময় স্ট্যাকে সংরক্ষণ করি এবং তারপর সেগুলো পপ করে লিস্ট রিভার্স করি; এই পদ্ধতিরও টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের লিস্টের আকার। পূর্বে আমরা স্ট্যাক ব্যবহার করতাম, তাই আমরা রিকার্সিভ পদ্ধতিও ব্যবহার করতে পারি কারণ সেটিও স্ট্যাক ব্যবহার করে, তাই এখন আমরা একটি রিকার্সিভ পদ্ধতি বানাব।
রিকার্সিভ পদ্ধতি
এই পদ্ধতিতে, আমরা আগের মতো একই প্রক্রিয়া করব কিন্তু রিকার্সিভ কল দিয়ে।
উদাহরণ প্রোগ্রাম
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
struct LinkedList {
Node* head;
LinkedList() { head = NULL; }
// লিংকড লিস্ট প্রিন্ট করার ফাংশন
void rreverse(Node* curr, Node* prev) {
if (curr == NULL) {
head = prev;
return;
}
rreverse(curr->next, curr);
curr->next = prev;
prev->next = NULL;
}
void reverse() {
auto curr = head; // কারেন্ট পয়েন্টার
Node* prev = NULL; // প্রিভিয়াস পয়েন্টার
rreverse(curr->next, curr);
}
void print() {
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}
void push(int data) {
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};
int main() {
LinkedList list;
list.push(20);
list.push(4);
list.push(15);
list.push(85);
list.print();
list.reverse();
cout << "\n";
list.print();
}
আউটপুট
85 15 4 20 20 4 15 85
এই পদ্ধতিতে, আমরা আগের মতো একই কাজ করছি কিন্তু রিকার্সিভ কল দিয়ে, তাই এই পদ্ধতিরও টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের লিস্টের আকার।
উপসংহার
এই আর্টিকেলে, আমরা সিংলি লিংকড লিস্ট রিভার্স করার সমস্যা সমাধান করেছি। আমরা এই সমস্যায় C++ প্রোগ্রাম এবং সম्पূর্ণ পদ্ধতি (নরমাল এবং দুইটি অন্য পদ্ধতি) শিখেছি যেগুলো দিয়ে আমরা এই সমস্যা সমাধান করেছি। আমরা একই প্রোগ্রাম অন্যান্য ল্যাঙ্গুয়েজে লিখতে পারি যেমন C, Java, Python এবং অন্যান্য ল্যাঙ্গুয়েজ। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
