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;}
输出before9 8 4 6after6 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;}
输出before9 8 4 6after6 4 8 9
上述代码的解释在这种方法中，我们使用一个堆栈，在遍历列表时填充该堆栈，然后将项目从堆栈中弹出并更改它们的值，以便列表是相反的。 o(n) 是该程序的时间复杂度，它也适用于更高的约束。
结论在本文中，我们解决了一个使用 or 反转双向链表的问题没有堆栈。时间复杂度为 o(n)，其中 n 是列表的大小。我们还学习了解决此问题的 c++ 程序以及解决此问题的完整方法（正常和非正统）。我们可以用其他语言比如c、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上就是使用c++反转一个双向链表的详细内容。