C++ を使用して二重リンクリストを反転する

この記事では、二重リンク リストがあり、C で二重リンク リストを逆にするさまざまな方法を説明します。たとえば、 -

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

通常は 1 つの方法が思い浮かびますが、ここでは通常の方法と型破りな方法の 2 つの方法を使用します。

通常の方法

この方法では、リストを確認し、確認しながらリストを逆にします。

例

#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 などの他の言語で書くことができます。この記事がお役に立てば幸いです。

以上がC++ を使用して二重リンクリストを反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。