এই নিবন্ধে, আমাদের এককভাবে লিঙ্ক করা তালিকার সাহায্যে লিঙ্কগুলিকে বিপরীত করতে হবে। আমাদের কাজ হল এমন একটি ফাংশন তৈরি করা যা প্রদত্ত এককভাবে লিঙ্ক করা তালিকাটিকে বিপরীত করতে সক্ষম। যেমন
Input: Following Linked list : 1->2->3->4->NULL Output: After processing of our function: 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; }
// Function to print linked list
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
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; }
// Function to print linked list
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
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; }
// Function to print linked list
void rreverse(Node *curr, Node *prev) {
if(curr == NULL) {
// prev -> next = curr;
head = prev;
return;
}
rreverse(curr -> next, curr);
curr -> next = prev;
prev -> next = NULL;
}
void reverse() {
auto curr = head; // current pointer
Node* prev = NULL; // previous pointer
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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ এবং অন্যান্য দুটি পন্থা) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
