Balikkan senarai berganda menggunakan C++

Dalam artikel ini, kami mempunyai senarai terpaut dua kali dan kami akan menerangkan cara berbeza untuk membalikkan senarai terpaut dua kali dalam C++. Contohnya -

Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}

Biasanya satu kaedah terlintas di fikiran, tetapi kita akan menggunakan dua kaedah - kaedah biasa dan kaedah tidak ortodoks.

Kaedah Biasa

Dalam kaedah ini, kita akan melalui senarai dan semasa kita melaluinya, kita membalikkannya.

Contoh

#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;
}

Output

Before
9 8 4 6
After
6 4 8 9

Kaedah ini memerlukan O(N)#🎜🎜 masa yang sangat kompleks🎜 kerana kerumitan ini boleh dilakukan di bawah kekangan yang lebih tinggi.

Kaedah Tidak Biasa

Seperti namanya, ini bukanlah kaedah yang biasa difikirkan oleh pengguna, tetapi kami juga akan meneroka kaedah ini. Dalam pendekatan ini kami akan membuat timbunan dan terus menolak data ke dalamnya dan pada pop kami akan menukar nilainya.

Contoh

#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;
}

Output

Before
9 8 4 6
After
6 4 8 9

Penjelasan kod di atas

#🎜 dalam pendekatan ini, kami menggunakan pendekatan ini🎜 isikan timbunan semasa anda mengulangi senarai, kemudian keluarkan item dari timbunan dan tukar nilainya supaya senarai itu diterbalikkan. O(N) ialah kerumitan masa program ini, yang juga digunakan untuk kekangan yang lebih tinggi.

Kesimpulan

Dalam artikel ini, kami menyelesaikan masalah membalikkan senarai terpaut dua kali menggunakan atau tanpa tindanan. Kerumitan masa ialah O(N), dengan N ialah saiz senarai. Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan kaedah lengkap (biasa dan tidak ortodoks) untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain seperti C, java, python dan bahasa lain. Kami berharap artikel ini dapat membantu anda.

Atas ialah kandungan terperinci Balikkan senarai berganda menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!