এই নিবন্ধে, আমরা একটি এককভাবে লিঙ্কযুক্ত তালিকার সাথে মোকাবিলা করি, এবং কাজটি হল k-এর গোষ্ঠীতে তালিকাটিকে বিপরীত করা। যেমন −
Input: 1->2->3->4->5->6->7->8->NULL, K = 3 Output: 3->2->1->6->5->4->8->7->NULL Input: 1->2->3->4->5->6->7->8->NULL, K = 5 Output: 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) { // we reverse the list till our count is less than k
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (next != NULL) // if our link list has not ended we call reverse function again
head->next = reverse(next, k);
return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
}
int main() {
Node* head = NULL;
int k = 3; // the given 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); // this function will return us our new head
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++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
