এই সমস্যায়, আমাদের একটি লিংকড লিস্টের হেড পয়েন্টার এবং একটি ইন্টিজার k দেওয়া আছে। k আকারের গ্রুপে আমাদের লিংকড লিস্টটি রিভার্স করতে হবে। উদাহরণস্বরূপ −
ইনপুট : 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 (ডাবলি লিংকড লিস্ট), k = 3 আউটপুট : 3 ↔ 2 ↔ 1 ↔ 5 ↔ 4
সমাধানের পদ্ধতি
এই সমস্যায়, আমরা একটি রিকার্সিভ অ্যালগরিদম বানাব এই সমস্যা সমাধান করার জন্য। এই পদ্ধতিতে, আমরা রিকার্সন ব্যবহার করব এবং সেটি দিয়ে সমস্যা সমাধান করব।
উদাহরণ প্রোগ্রাম
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// লিস্টে নোড পুশ করার ফাংশন
Node* push(Node* head, int data) {
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
Node* TMP = head;
if (head == NULL) {
new_node->prev = NULL;
head = new_node;
return head;
}
while (TMP->next != NULL) { // লাস্ট নোডে যাওয়া
TMP = TMP->next;
}
TMP->next = new_node;
new_node->prev = TMP;
return head; // হেড পয়েন্টার রিটার্ন
}
// দেয়া লিস্ট প্রিন্ট করার ফাংশন
void printDLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
Node* revK(Node* head, int k) {
if (!head)
return NULL;
head->prev = NULL;
Node *TMP, *CURRENT = head, *newHead;
int count = 0;
while (CURRENT != NULL && count < k) { // যতক্ষণ কাউন্ট k-র চেয়ে কম, সিম্পলি নোডগুলো রিভার্স করব
newHead = CURRENT;
TMP = CURRENT->prev;
CURRENT->prev = CURRENT->next;
CURRENT->next = TMP;
CURRENT = CURRENT->prev;
count++;
}
if (count >= k) {
head->next = revK(CURRENT, k); // এখন যদি কাউন্ট k-র চেয়ে বড় বা সমান হয়, আমরা ফার্স্ট হেডকে নেক্স্ট হেডের সাথে কানেক্ট করব
}
return newHead;
}
int main() {
Node* head;
for (int i = 1; i <= 5; i++) {
head = push(head, i);
}
cout << "Original List : ";
printDLL(head);
cout << "\nModified List : ";
int k = 3;
head = revK(head, k);
printDLL(head);
}
আউটপুট
Original List : 1 2 3 4 5 Modified List : 3 2 1 5 4
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা লিস্ট ট্রাভার্স করছি এবং কাউন্ট k-র চেয়ে কম থাকা পর্যন্ত ট্রাভার্স করছি। আমরা একটি রিকার্সিভ কল দিচ্ছি যেটি হেড-→next-এ মান পাস করছে (এখানে আমরা সিম্পলি লিস্ট রিভার্স করছি ট্রাভার্স করার সময়, কিন্তু যখন k পৌঁছায়, আমাদের হেডকে অন্য লিস্টের kth এলিমেন্টের দিকে পয়েন্ট করতে হবে। উদাহরণস্বরূপ, যদি লিস্ট 1 2 3 4 5 হয় এবং k=3 হয়, তবে আমরা মিডেল এলিমেন্টগুলো 3 2 1 করে রিভার্স করব কিন্তু এখন আমাদের 1 কে 4-কে পয়েন্ট করতে হবে কারণ সেটিও রিভার্স হব, তাই আমরা রিকার্সিভ কল এবং এক্সট্রা if স্টেটমেন্ট ব্যবহার করছি।)
উপসংহার
এই আর্টিকেলে, আমরা রিকার্সন ব্যবহার করে দেয়া সাইজের গ্রুপে ডাবলি-লিংকড লিস্ট রিভার্স করার সমস্যা সমাধান করেছি। আমরা এই সমস্যায় C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি শিখেছি। আমরা একই প্রোগ্রাম অন্যান্য ল্যাঙ্গুয়েজে লিখতে পারি যেমন C, Java, Python এবং অন্যান্য ল্যাঙ্গুয়েজ। আশা করি আপনি এই আর্টিকেলটিকে সহায়ক খুঁজে পাবেন।
