使用 C++ 反转双向链表
在本文中,我们有一个双向链表,我们将解释在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)非常好的时间复杂度,因为这种复杂度可以在更高的约束下执行。
非正统的方法
顾名思义,这不是用户想到的一种很常见的方法,但是我们将探索这种方法作为well.In这种方法,我们将创建一个堆栈并不断向其中推送数据,在弹出的同时,我们将更改其值。
示例
#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)是这个程序的时间复杂度,它也适用于更高的约束。
结论
在这篇文章中,我们解决了一个有栈或没有栈的双向链表反转的问题。在O(N)时间复杂度中,N是我们list.We针对这个问题学习的C++程序的大小,以及我们解决这个问题的完整方法(Normal和Unorthodox)。我们可以用C、java、python等其他语言编写相同的程序。我们希望这篇文章对您有所帮助。