Trong bài toán này, ta được cho con trỏ đến đầu danh sách liên kết và một số nguyên k. Theo nhóm kích thước k, ta cần đảo ngược danh sách liên kết. Ví dụ −
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (danh sách liên kết đôi), k = 3 Output : 3 <-> 2 <-> 1 <-> 5 <-> 4
Phương pháp tìm giải pháp
Trong bài toán này, ta sẽ tạo thuật toán đệ quy để giải quyết. Trong phương pháp này, ta sẽ dùng đệ quy và giải quyết bài toán bằng cách đó.
Ví dụ
#include <iostream> using namespace std; struct Node { int data; Node *next, *prev; }; // hàm push để đẩy nút vào danh sách Node* push(Node* head, int data) { Node* new_node = new Node(); new_node->data = data; new_node->next = NULL; Node* TMP = head; if (head == NULL) { new_node->prev = NULL; head = new_node; return head; } while (TMP->next != NULL) { // đi đến nút cuối TMP = TMP->next; } TMP->next = new_node; new_node->prev = TMP; return head; // trả về con trỏ đến head } // hàm in danh sách cho trước void printDLL(Node* head) { while (head != NULL) { cout << head->data << " "; head = head->next; } cout << endl; } Node* revK(Node* head, int k) { if (!head) return NULL; head->prev = NULL; Node *TMP, *CURRENT = head, *newHead; int count = 0; while (CURRENT != NULL && count < k) { // trong khi count nhỏ hơn k ta đơn giản đảo ngược các nút. newHead = CURRENT; TMP = CURRENT->prev; CURRENT->prev = CURRENT->next; CURRENT->next = TMP; CURRENT = CURRENT->prev; count++; } if (count >= k) { head->next = revK(CURRENT, k); // bây giờ nếu count lớn hơn hoặc bằng //k ta nối head đầu tiên đến head tiếp theo } return newHead; } int main() { Node* head; for (int i = 1; i <= 5; i++) { head = push(head, i); } cout << "Original List : "; printDLL(head); cout << "\nModified List : "; int k = 3; head = revK(head, k); printDLL(head); } Kết quả
Original List : 1 2 3 4 5 Modified List : 3 2 1 5 4
Giải thích mã trên
Trong phương pháp này, ta duyệt qua danh sách và duyệt cho đến khi count nhỏ hơn k. Ta tạo lời gọi đệ quy đưa giá trị đó cho head->next (ở đây ta đơn giản đảo ngược danh sách khi đi qua, nhưng khi k đạt đến, ta cần head trỏ đến phần tử thứ k của danh sách khác. Ví dụ, nếu danh sách là 1 2 3 4 5 và k là 3, ta đảo phần giữa thành 3 2 1 nhưng bây giờ ta cần 1 trỏ đến 4 vì phần tử đó cũng sẽ bị đảo ngược, đó là lý do ta dùng lời gọi đệ quy và câu lệnh if bổ sung.).
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 theo nhóm kích thước cho trước bằng đệ quy. 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 ta đã giải quyết. 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.