इस समस्या में, हमें एक लिंक की गई सूची के शीर्ष पर एक सूचक और एक पूर्णांक k दिया जाता है। k आकार के समूहों में, हमें लिंक की गई सूची को उलटने की आवश्यकता है। उदाहरण के लिए -
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3 Output : 3 <-> 2 <-> 1 <-> 5 <-> 4
समाधान खोजने के लिए दृष्टिकोण
इस समस्या में, हम इस समस्या को हल करने के लिए एक पुनरावर्ती एल्गोरिथ्म बनाने जा रहे हैं। इस दृष्टिकोण में, हम रिकर्सन का उपयोग करने जा रहे हैं और इसका उपयोग करके समस्या का समाधान करेंगे।
उदाहरण
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// push function to push a node into the list
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) { // going to the last node
TMP = TMP->next;
}
TMP->next = new_node;
new_node->prev = TMP;
return head; // return pointer to head
}
// function to print given list
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) { // while our count is less than k we simply reverse the nodes.
newHead = CURRENT;
TMP = CURRENT->prev;
CURRENT->prev = CURRENT->next;
CURRENT->next = TMP;
CURRENT = CURRENT->prev;
count++;
}
if (count >= k) {
head->next = revK(CURRENT, k); // now when if the count is greater or equal
//to k we connect first head to next head
}
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 से कम न हो जाए। हम करते हैं और रिकर्सिव कॉल हेड को वह मान देते हैं -> अगला (यहां हम सूची को उलट रहे हैं जैसे हम जाते हैं, लेकिन जब हमारे के तक पहुंच जाता है, तो हमें अपने सिर को अन्य सूचियों के लिए इंगित करने की आवश्यकता होती है उदाहरण के लिए, यदि हमारा सूची 1 2 3 4 5 है और हमारा k 3 है इसमें हम मध्य तत्वों को 3 2 1 पर उलट देते हैं लेकिन अब हमें 1 से 4 को इंगित करने की आवश्यकता है क्योंकि वह तत्व भी उलट होने वाला है, इसलिए हम इसका उपयोग कर रहे हैं रिकर्सिव कॉल और एक अतिरिक्त if स्टेटमेंट बनाना।)।
निष्कर्ष
इस लेख में, हम पुनरावृत्ति का उपयोग करके किसी दिए गए आकार के समूहों में एक डबल-लिंक्ड सूची को उलटने के लिए एक समस्या का समाधान करते हैं . हमने इस समस्या के लिए C++ प्रोग्राम और हमारे द्वारा हल किए गए संपूर्ण दृष्टिकोण को भी सीखा। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।