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はリストのサイズです。

次に、リストを逆にするためにスタックを使用しようとする1つの実験を試みます。

スタックを使用したアプローチ

スタックを使用してこのプログラムのすべてのノードを格納し、スタックを通過してそれらを逆にします。

例

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