資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 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)，也適用於更高的約束條件。
結論
在本文中，我們解決了一個問題，即使用或不使用棧反轉雙向連結串列。時間複雜度為 O(N)，其中 N 是列表的大小。我們還學習了該問題的 C++ 程式以及我們解決該問題的完整方法（常規方法和非常規方法）。我們可以在其他語言（如 C、Java、Python 和其他語言）中編寫相同的程式。希望本文對您有所幫助。
更新於: 2021年11月29日
567 次檢視
廣告