使用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)時間複雜度，這是非常好的，因為這種複雜度可以在更高的限制下執行。

非正統方法

作為顧名思義，這不是使用者想到的一種非常常見的方法，但我們也會探索這種方法。在這種方法中，我們將建立一個堆疊並不斷向其中推送數據，在彈出時我們將更改它的值。

範例

#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中文網其他相關文章！