Trong bài viết này ta có một danh sách liên kết đôi, và ta sẽ giải thích các phương pháp khác nhau để đảo ngược danh sách liên kết đôi trong C++. Ví dụ −
Input : {1, 2, 3, 4} Output : {4, 3, 2, 1}Thông thường chỉ có một phương pháp nảy ra trong đầu, nhưng ta sẽ dùng hai phương pháp − Phương pháp bình thường và phương pháp phi truyền thống.
Phương pháp bình thường
Trong phương pháp này, ta sẽ đi qua danh sách, và trong khi đi qua, ta đả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; }Kết quả
Before 9 8 4 6 After 6 4 8 9
Phương pháp này có độ phức tạp thời gian O(N) rất tốt vì độ phức tạp này có thể thực thi với các ràng buộc cao.
Phương pháp phi truyền thống
Như tên gợi ý, đây không phải phương pháp phổ biến nảy ra trong đầu người dùng, nhưng ta sẽ khám phá phương pháp này. Trong phương pháp này, ta sẽ tạo một stack và đẩy dữ liệu vào, và khi lấy ra, ta sẽ thay đổi giá trị của chúng.
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; }Kết quả
Before 9 8 4 6 After 6 4 8 9
Giải thích mã trên
Trong phương pháp này ta dùng stack được lấp đầy khi duyệt qua danh sách và sau đó lấy các phần tử ra khỏi stack 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 thời gian của chương trình này và nó phù hợp với các ràng buộc cao.
Kết luận
Trong bài viết này ta giải quyết bài toán đảo ngược danh sách liên kết đôi có hoặc không có stack. Với độ phức tạp thời gian O(N) trong đó N là kích thước danh sách. Ta cũng học chương trình C++ cho bài toán này và phương pháp hoàn chỉnh (Bình thường và Phi truyền thống) để giải quyết bài toán. Ta có thể viết cùng chương trình bằng ngôn ngữ khác như C, Java, Python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết hữu ích.