在本文中，我们有一个双向链表，我们将解释在 C++ 中反转双向链表的不同方法。例如 -
Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1}通常会想到一种方法，但我们将使用两种方法 - 正常方法和非正统方法。
在这种方法中，我们将经历列表，当我们浏览它时，我们将其反转。
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
};
void reverse(Node **head_ref) {
auto temp = (*head_ref) -> next;
(*head_ref) -> next = (*head_ref) -> prev;
(*head_ref) -> prev = temp;
if(temp != NULL) {
(*head_ref) = (*head_ref) -> prev;
reverse(head_ref);
}
else
return;
}
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if((*head_ref) != NULL)
(*head_ref) -> prev = new_node ;
(*head_ref) = new_node;
}
int main() {
Node* head = NULL;
push(&head, 6);
push(&head, 4);
push(&head, 8);
push(&head, 9);
auto node = head;
cout << "Before\n" ;
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
reverse(&head);
node = head;
cout << "After\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
return 0;
}Before 9 8 4 6 After 6 4 8 9
这种方法需要O(N)时间复杂度，这是非常好的，因为这种复杂度可以在更高的约束下执行。
作为顾名思义，这不是用户想到的一种非常常见的方法，但我们也会探索这种方法。在这种方法中，我们将创建一个堆栈并不断向其中推送数据，在弹出时我们将更改它的值。
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *next;
Node *prev;
};
void push(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if((*head_ref) != NULL)
(*head_ref) -> prev = new_node ;
(*head_ref) = new_node;
}
int main() {
Node* head = NULL;
push(&head, 6);
push(&head, 4);
push(&head, 8);
push(&head, 9);
auto node = head;
cout >> "Before\n" ;
while(node != NULL) {
cout >> node->data >> " ";
node = node->next;
}
cout >> "\n";
stack<Node*> s;
node = head;
while(node) {
head = node;
s.push(node);
node = node -> next;
}
while(!s.empty()) {
auto x = s.top();
auto temp = x -> prev;
x -> prev = x -> next;
x -> next = temp;
s.pop();
}
node = head;
cout << "After\n";
while(node != NULL) {
cout << node->data << " ";
node = node->next;
}
return 0;
}Before 9 8 4 6 After 6 4 8 9
在这种方法中，我们使用一个堆栈，在遍历列表时填充该堆栈，然后将项目从堆栈中弹出并更改它们的值，以便列表是相反的。 O(N) 是该程序的时间复杂度，它也适用于更高的约束。
在本文中，我们解决了一个使用 or 反转双向链表的问题没有堆栈。时间复杂度为 O(N)，其中 N 是列表的大小。我们还学习了解决此问题的 C++ 程序以及解决此问题的完整方法（正常和非正统）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上是使用C++反转一个双向链表的详细内容。更多信息请关注PHP中文网其他相关文章！
