এই আর্টিকেলে, আমরা একটি সিংলি লিংকড লিস্ট নিয়ে কাজ করব, এবং কাজ হল লিস্টটি k আকারের গ্রুপে রিভার্স করা। উদাহরণস্বরূপ −
ইনপুট: 1→2→3→4→5→6→7→8→NULL, K = 3 আউটপুট: 3→2→1→6→5→4→8→7→NULL ইনপুট: 1→2→3→4→5→6→7→8→NULL, K = 5 আউটপুট: 5→4→3→2→1→8
এই সমস্যার জন্য, একটা পদ্ধতি মনে আসে: লিস্ট ট্রাভার্স করা এবং যখন আমাদের সাবলিস্টের সাইজ k-এ পৌঁছায়, তখন সেটি রিভার্স করা এবং এগিয়ে যাওয়া।
সমাধানের পদ্ধতি
এই পদ্ধতিতে, আমরা সাধারণভাবে লিস্ট ট্রাভার্স করব এবং একটি কাউন্টার রাখব আমাদের সাব-লিস্টের উপাদান সংখ্যা গুনতে। যখন কাউন্টার k-এ পৌঁছাবে, আমরা সেটি রিভার্স করব।
উদাহরণ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* reverse(Node* head, int k) {
if (!head)
return NULL;
Node* curr = head;
Node* next = NULL;
Node* prev = NULL;
int count = 0;
while (curr != NULL && count < k) { // আমরা লিস্ট রিভার্স করব যতক্ষণ কাউন্ট k-র চেয়ে কম
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (next != NULL) // যদি লিংকড লিস্ট শেষ না হয়, আবার রিভার্স ফাংশন কল করব
head->next = reverse(next, k);
return prev;
}
void push(Node** head_ref, int new_data) { // লিস্টে ডেটা পুশ করার ফাংশন
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node) { // লিংকড লিস্ট প্রিন্ট করার ফাংশন
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
}
int main() {
Node* head = NULL;
int k = 3; // দেওয়া k
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "Original list \n";
printList(head);
head = reverse(head, k); // এই ফাংশন আমাদের নতুন হেড রিটার্ন করবে
cout << "New list \n";
printList(head);
return (0);
}
আউটপুট
Original list 1 2 3 4 5 6 7 8 New list 3 2 1 6 5 4 8 7
উপরোক্ত পদ্ধতির টাইম কমপ্লেক্সিটি O(N), যেখানে N হল আমাদের দেয়া লিস্টের আকার, এবং এই পদ্ধতি রিকার্সিভ ভাবে কাজ করে। এই পদ্ধতি উচ্চ কনস্ট্রেইন্টের জন্যও কাজ করতে পারে।
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা অ্যারে ট্রাভার্স করব এবং কাউন্টার ভেরিয়েবল k-র চেয়ে কম থাকা পর্যন্ত রিভার্স করব। যখন কাউন্টার k-এর মান পৌঁছাবে, আমরা আরেকটি রিভার্সিং ফাংশন কল করব এই সাব-লিস্টের লাস্ট নোডকে পরবর্তী রিভার্সড সাব-লিস্টের ফার্স্ট নোডের সাথে কানেক্ট করার জন্য। এটি রিকার্সন দিয়ে করা হচ্ছে।
উপসংহার
এই আর্টিকেলে, আমরা রিকার্সন ব্যবহার করে দেয়া সাইজের গ্রুপে লিংকড লিস্ট রিভার্স করার সমস্যা সমাধান করেছি। আমরা এই সমস্যায় C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (নরমাল) শিখেছি যেগুলো দিয়ে আমরা এই সমস্যা সমাধান করেছি। আমরা একই প্রোগ্রাম অন্যান্য ল্যাঙ্গুয়েজে লিখতে পারি যেমন C, Java, Python এবং অন্যান্য ল্যাঙ্গুয়েজ। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
