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

この記事では、単一リンク リストを使用してリンクを逆にする必要があります。私たちのタスクは、指定された単一リンク リストを反転できる関数を作成することです。たとえば、

Input:
Following Linked list :
1->2->3->4->NULL

Output:
After processing of our function:
4->3->2->1->NULL

解決策を見つける方法

リンク リストを反転するにはさまざまな方法があります。通常、リンク リストをトラバースしながら、リンク リストを逆にする簡単な方法を考えます。

簡単な方法

この方法では、リンクされたリストを走査し、走査中にそれを逆にしようとします。

例

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      while(curr) {
         auto temp = curr -> next;
         curr -> next = prev;
         prev = curr;
         head = prev;
         curr = temp;
      }
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

出力

85 15 4 20
20 4 15 85

このアプローチでは、リストを反復処理するだけで、反復中にそれを逆にします。時間計算量が O(N) (N はリストのサイズ) であるため、これは良いアプローチです。

ここで実験を行って、スタックを使用してリストを反転してみます。

スタックを使用したメソッド

スタックを使用して、このプログラム内のすべてのノードを保存し、スタックを走査することでノードを反転します。

例

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
   }
};
struct LinkedList {
   Node* head;
   LinkedList() { head = NULL; }
   // Function to print linked list
   void reverse() {
      auto curr = head; // current pointer
      Node* prev = NULL; // previous pointer
      stack<Node *> s;
      while(curr) {
         s.push(curr);
         curr = curr -> next;
      }
      prev = s.top();
      head = prev;
      s.pop();
      while(!s.empty()) {
         auto temp = s.top();
         s.pop();
         prev -> next = temp;
         prev = temp;
      }
      prev -> next = NULL;
   }
   void print() {
      struct Node* temp = head;
      while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

出力

85 15 4 20
20 4 15 85

上記のコードの説明

このメソッドでは、リストを走査しながらリスト ノードをスタックに保存します。スタックを使用してそれらをポップし、リストを反転します。このアプローチの時間計算量も O(N) です (N はリストのサイズです)。前と同様にスタックを使用したので、再帰メソッドも使用できます。再帰でもスタックが使用されるためです。ここでは再帰メソッドを使用します。

再帰メソッド

このメソッドでは、再帰呼び出しを使用して、前と同じプロセスを実行します。

例

#include<bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
   Node(int data) {
      this->data = data;
      next = NULL;
      }
   };
   struct LinkedList {
      Node* head;
      LinkedList() { head = NULL; }
      // Function to print linked list
      void rreverse(Node *curr, Node *prev) {
         if(curr == NULL) {
            // prev -> next = curr;
            head = prev;
            return;
         }
         rreverse(curr -> next, curr);
         curr -> next = prev;
         prev -> next = NULL;
      }

      void reverse() {
         auto curr = head; // current pointer
         Node* prev = NULL; // previous pointer
         rreverse(curr -> next, curr);
      }
      void print() {
         struct Node* temp = head;
         while (temp != NULL) {
         cout << temp->data << " ";
         temp = temp->next;
      }
   }
   void push(int data) {
      Node* temp = new Node(data);
      temp->next = head;
      head = temp;
   }
};
int main() {
   LinkedList list;
   list.push(20);
   list.push(4);
   list.push(15);
   list.push(85);
   list.print();
   list.reverse();
   cout << "\n";
   list.print();
}

出力

85 15 4 20
20 4 15 85

このメソッドでは前と同じことを行っていますが、再帰呼び出しを使用しているため、このメソッドの時間計算量も O( N)、ここで N はリストのサイズです。

結論

この記事では、単一リンク リストの反転の問題を解決しました。また、この問題を解決するための C プログラムと完全な方法 (通常の方法と他の 2 つの方法) も学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。この記事がお役に立てば幸いです。

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