使用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 程序和完整的方法（普通方法和其他兩種方法）。我們可以用其他語言（如C、Java、Python和其他語言）編寫相同的程式。希望您會覺得這篇文章有幫助。

以上是使用C++反轉一個鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！