C++ का उपयोग करके एक दोहरी लिंक की गई सूची को उलट दें

इस लेख में हमारे पास एक डबल लिंक्ड लिस्ट है, और हम 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) इस कार्यक्रम की समय जटिलता है और यह उच्च बाधाओं के लिए भी उपयुक्त है।

निष्कर्ष

इस लेख में हम स्टैक के साथ या बिना डबल लिंक की गई सूची को उलटने की समस्या का समाधान करते हैं। ओ (एन) समय जटिलता में जहां एन हमारी सूची का आकार है। हमने इस समस्या के लिए सी ++ प्रोग्राम और पूर्ण दृष्टिकोण (सामान्य और अपरंपरागत) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे C, java, python और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।