इस समस्या में, हमें एक लिंक्ड लिस्ट के हेड का पॉइंटर और एक पूर्णांक k दिया गया है। आकार k के समूहों में, हमें लिंक्ड लिस्ट को रिवर्स करना होगा। उदाहरण के लिए −
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (डबल लिंक्ड लिस्ट), k = 3 Output : 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 पहुंच जाता है, तो हमें अपने हेड को दूसरे लिस्ट के kवें एलिमेंट की ओर इंगित करने की आवश्यकता होती है, उदाहरण के लिए, यदि हमारी लिस्ट 1 2 3 4 5 है और हमारा k 3 है, तो इसमें हम मध्य एलिमेंट्स को 3 2 1 में रिवर्स करते हैं लेकिन अब हमें अपने 1 को 4 की ओर इंगित करने की आवश्यकता है क्योंकि वह एलिमेंट भी रिवर्स होने वाला है, इसलिए हम रिकर्सिव कॉल का उपयोग कर रहे हैं और एक अतिरिक्त if स्टेटमेंट बना रहे हैं।)
निष्कर्ष
इस लेख में, हम रिकर्सन का उपयोग करके दिए गए आकार के समूहों में डबल लिंक्ड लिस्ट को रिवर्स करने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और हमारे द्वारा हल किए गए पूर्ण दृष्टिकोण को भी सीखा। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगा होगा।