इस लेख में हमारे पास एक डबल लिंक्ड लिस्ट है, और हम C++ में डबल लिंक्ड लिस्ट को रिवर्स करने के विभिन्न दृष्टिकोणों की व्याख्या करेंगे। उदाहरण के लिए −
Input : {1, 2, 3, 4} Output : {4, 3, 2, 1}आम तौर पर एक दृष्टिकोण दिमाग में आता है, लेकिन हम दो दृष्टिकोणों का उपयोग करेंगे − सामान्य और अपरंपरागत दृष्टिकोण।
सामान्य दृष्टिकोण
इस दृष्टिकोण में, हम लिस्ट के माध्यम से जाएंगे, और जैसे-जैसे हम इसके माध्यम से जाते हैं, हम इसे रिवर्स करते हैं।
उदाहरण
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *next; Node *prev; }; void reverse(Node **head_ref) { auto temp = (*head_ref) -> next; (*head_ref) -> next = (*head_ref) -> prev; (*head_ref) -> prev = temp; if(temp != NULL) { (*head_ref) = (*head_ref) -> prev; reverse(head_ref); } else return; } void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head_ref); if((*head_ref) != NULL) (*head_ref) -> prev = new_node ; (*head_ref) = new_node; } int main() { Node* head = NULL; push(&head, 6); push(&head, 4); push(&head, 8); push(&head, 9); auto node = head; cout << "Before\n" ; while(node != NULL) { cout << node->data << " "; node = node->next; } cout << "\n"; reverse(&head); node = head; cout << "After\n"; while(node != NULL) { cout << node->data << " "; node = node->next; } return 0; }आउटपुट
Before 9 8 4 6 After 6 4 8 9
यह दृष्टिकोण O(N) समय जटिलता लेता है जो बहुत अच्छा है क्योंकि यह जटिलता उच्च प्रतिबंधों में प्रदर्शन कर सकती है।
अपरंपरागत दृष्टिकोण
जैसा कि नाम से पता चलता है, यह एक बहुत ही सामान्य दृष्टिकोण नहीं है जो उपयोगकर्ता के दिमाग में आता है, लेकिन हम इस दृष्टिकोण का भी पता लगाएंगे। इस दृष्टिकोण में, हम एक स्टैक बनाएंगे और उसमें डेटा डालते रहेंगे, और पॉप करते समय, हम इसके मानों को बदलने जा रहे हैं।
उदाहरण
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node *next; Node *prev; }; void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->prev = NULL; new_node->next = (*head_ref); if((*head_ref) != NULL) (*head_ref) -> prev = new_node ; (*head_ref) = new_node; } int main() { Node* head = NULL; push(&head, 6); push(&head, 4); push(&head, 8); push(&head, 9); auto node = head; cout << "Before\n" ; while(node != NULL) { cout << node->data << " "; node = node->next; } cout << "\n"; stack<Node*> s; node = head; while(node) { head = node; s.push(node); node = node -> next; } while(!s.empty()) { auto x = s.top(); auto temp = x -> prev; x -> prev = x -> next; x -> next = temp; s.pop(); } node = head; cout << "After\n"; while(node != NULL) { cout << node->data << " "; node = node->next; } return 0; }आउटपुट
Before 9 8 4 6 After 6 4 8 9
उपरोक्त कोड की व्याख्या
इस दृष्टिकोण में हम एक स्टैक का उपयोग कर रहे हैं जिसे हम लिस्ट के माध्यम से ट्रैवर्स करते समय भर रहे हैं और फिर हम स्टैक से आइटम पॉप कर रहे हैं और उनके मानों को इस तरह बदल रहे हैं कि लिस्ट रिवर्स हो जाए। इस प्रोग्राम की समय जटिलता O(N) है और यह उच्च प्रतिबंधों के लिए भी उपयुक्त है।
निष्कर्ष
इस लेख में हम स्टैक के साथ या बिना डबल लिंक्ड लिस्ट को रिवर्स करने की समस्या को हल करते हैं। O(N) समय जटिलता में जहां N हमारी लिस्ट का आकार है। हमने इस समस्या के लिए C++ प्रोग्राम और पूर्ण दृष्टिकोण (सामान्य और अपरंपरागत) सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगा होगा।