数据结构
网络
关系数据库管理系统
操作系统
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+ 阅读量
广告