使用 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等其他语言编写相同的程序。我们希望这篇文章对您有所帮助。