इस लेख में, हम एक सिंगली लिंक्ड लिस्ट से निपटते हैं, और कार्य 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, जावा, पायथन और अन्य भाषाओं में भी वही प्रोग्राम लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख उपयोगी लगा होगा।
