Trong bài viết này, chúng ta cần đảo ngược các liên kết với sự giúp đỡ của danh sách liên kết đơn. Nhiệm vụ của chúng ta là tạo một hàm có khả năng đảo ngược danh sách liên kết đơn cho trước. Ví dụ
Input: Danh sách liên kết sau : 1->2->3->4->NULL Output: Sau khi xử lý hàm: 4->3->2->1->NULL
Phương pháp tìm giải pháp
Có nhiều phương pháp khác nhau để đảo ngược danh sách liên kết. Thông thường, một phương pháp đơn giản nảy ra trong đầu là duyệt danh sách và đảo ngược nó trong khi đi qua.
Phương pháp đơn giản
Ta sẽ đi qua danh sách liên kết trong phương pháp này và cố gắng đảo ngược nó trong khi đi qua.
Ví dụ
#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; Node(int data) { this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList() { head = NULL; } // Hàm in danh sách liên kết void reverse() { auto curr = head; // con trỏ hiện tại Node* prev = NULL; // con trỏ trước while(curr) { auto temp = curr -> next; curr -> next = prev; prev = curr; head = prev; curr = temp; } } void print() { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; } }; int main() { LinkedList list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); }Kết quả
85 15 4 20 20 4 15 85
Trong phương pháp này, ta đơn giản duyệt qua danh sách và đảo ngược khi đi qua. Đây là phương pháp tốt vì độ phức tạp thời gian là O(N), trong đó N là kích thước danh sách.
Bây giờ ta thử một thí nghiệm dùng stack để đảo ngược danh sách.
Phương pháp dùng Stack
Trong chương trình này, ta sẽ dùng stack để lưu tất cả các nút và đảo ngược chúng bằng cách duyệt qua stack.
Ví dụ
#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; Node(int data) { this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList() { head = NULL; } // Hàm in danh sách liên kết void reverse() { auto curr = head; // con trỏ hiện tại Node* prev = NULL; // con trỏ trước stack<Node *> s; while(curr) { s.push(curr); curr = curr -> next; } prev = s.top(); head = prev; s.pop(); while(!s.empty()) { auto temp = s.top(); s.pop(); prev -> next = temp; prev = temp; } prev -> next = NULL; } void print() { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; } }; int main() { LinkedList list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); } Kết quả
85 15 4 20 20 4 15 85
Giải thích mã trên
Trong phương pháp này, ta lưu các nút danh sách vào stack khi duyệt và dùng stack để lấy ra và đảo ngược danh sách; phương pháp này cũng có độ phức tạp thời gian O(N), N là kích thước danh sách. Vì trước ta dùng stack, ta cũng có thể dùng phương pháp đệ quy vì cũng dùng stack, nên ta sẽ làm phương pháp đệ quy.
Phương pháp đệ quy
Trong phương pháp này, ta sẽ làm cùng quy trình như trước nhưng với lời gọi đệ quy.
Ví dụ
#include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node* next; Node(int data) { this->data = data; next = NULL; } }; struct LinkedList { Node* head; LinkedList() { head = NULL; } // Hàm in danh sách liên kết void rreverse(Node *curr, Node *prev) { if(curr == NULL) { // prev -> next = curr; head = prev; return; } rreverse(curr -> next, curr); curr -> next = prev; prev -> next = NULL; } void reverse() { auto curr = head; // con trỏ hiện tại Node* prev = NULL; // con trỏ trước rreverse(curr -> next, curr); } void print() { struct Node* temp = head; while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } } void push(int data) { Node* temp = new Node(data); temp->next = head; head = temp; } }; int main() { LinkedList list; list.push(20); list.push(4); list.push(15); list.push(85); list.print(); list.reverse(); cout << "\n"; list.print(); }Kết quả
85 15 4 20 20 4 15 85
Trong phương pháp này, ta làm giống như trước nhưng với lời gọi đệ quy, nên phương pháp này cũng có độ phức tạp thời gian O(N), N là kích thước danh sách.
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 đơn. Ta cũng học chương trình C++ cho bài toán này và các phương pháp hoàn chỉnh (Bình thường và hai phương pháp khác) để 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.