Trong bài viết này, chúng tôi có danh sách liên kết kép và chúng tôi sẽ giải thích các cách tiếp cận khác nhau để đảo ngược danh sách liên kết kép trong C ++. Ví dụ -
Input : {1, 2, 3, 4}
Output : {4, 3, 2, 1} Nhìn chung, có một cách tiếp cận nghĩ đến, nhưng chúng tôi sẽ sử dụng hai cách tiếp cận - Cách tiếp cận bình thường và không chính thống.
Phương pháp tiếp cận thông thường
Trong cách tiếp cận này, chúng tôi sẽ xem qua danh sách và khi chúng tôi xem qua nó, chúng tôi đảo ngược nó.
Ví dụ
#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;
} Đầu ra
Before 9 8 4 6 After 6 4 8 9
Cách tiếp cận này sử dụng O (N) độ phức tạp về thời gian là rất tốt vì độ phức tạp này có thể thực hiện trong các ràng buộc cao hơn.
Phương pháp tiếp cận không chính thống
Như tên cho thấy, đây không phải là một cách tiếp cận phổ biến trong suy nghĩ của người dùng, nhưng chúng tôi cũng sẽ khám phá cách tiếp cận này. để thay đổi các giá trị của nó.
Ví dụ
#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;
} Đầu ra
Before 9 8 4 6 After 6 4 8 9
Giải thích về Quy tắc trên
Trong cách tiếp cận này, chúng tôi đang sử dụng một ngăn xếp mà chúng tôi đang điền trong khi duyệt qua danh sách và sau đó chúng tôi đưa các mục ra khỏi ngăn xếp và thay đổi giá trị của chúng sao cho danh sách bị đảo ngược. O (N) là độ phức tạp về thời gian của chương trình này và nó cũng phù hợp với các ràng buộc cao hơn.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề đảo ngược danh sách được liên kết kép có hoặc không có ngăn xếp. Trong độ phức tạp thời gian O (N), trong đó N là kích thước của danh sách của chúng tôi, chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và Không chính thống) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết chương trình tương tự bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.