在這篇文章中，我們需要藉助單鍊錶來反轉連結。我們的任務是創建一個能夠反轉給定單鍊錶的函數。例如
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中文網其他相關文章！
