資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 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 和其他語言）編寫相同的程式。希望本文對您有所幫助。
更新於: 2021年11月29日
3K+ 閱讀量
廣告