在本文中，我们有一个双向链表，我们将解释在 C++ 中反转双向链表的不同方法。例如 –
Input : {1, 2, 3, 4}Output : {4, 3, 2, 1}
登录后复制
通常会想到一种方法，但我们将使用两种方法 – 正常方法和非正统方法。
正常方法
在这种方法中，我们将经历列表，当我们浏览它时，我们将其反转。
示例
#include 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 data next; } cout data next; } return 0;}
登录后复制
输出
Before9 8 4 6After6 4 8 9
登录后复制登录后复制
这种方法需要O(N)时间复杂度，这是非常好的，因为这种复杂度可以在更高的约束下执行。
立即学习“C++免费学习笔记（深入）”；
非正统方法
作为顾名思义，这不是用户想到的一种非常常见的方法，但我们也会探索这种方法。在这种方法中，我们将创建一个堆栈并不断向其中推送数据，在弹出时我们将更改它的值。
示例
#include 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" ; while(node != NULL) { cout >> node->data >> " "; node = node->next; } cout >> ""; stack 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 data next; } return 0;}
登录后复制
输出
Before9 8 4 6After6 4 8 9
登录后复制登录后复制
上述代码的解释
在这种方法中，我们使用一个堆栈，在遍历列表时填充该堆栈，然后将项目从堆栈中弹出并更改它们的值，以便列表是相反的。 O(N) 是该程序的时间复杂度，它也适用于更高的约束。
结论
在本文中，我们解决了一个使用 or 反转双向链表的问题没有堆栈。时间复杂度为 O(N)，其中 N 是列表的大小。我们还学习了解决此问题的 C++ 程序以及解决此问题的完整方法（正常和非正统）。我们可以用其他语言比如C、java、python等语言来编写同样的程序。我们希望这篇文章对您有所帮助。
以上就是使用C++反转一个双向链表的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2584763.html
