Trong bài viết này, ta xử lý danh sách liên kết đơn, và nhiệm vụ là đảo ngược danh sách theo nhóm kích thước k. Ví dụ −
Input: 1->2->3->4->5->6->7->8->NULL, K = 3 Output: 3->2->1->6->5->4->8->7->NULL Input: 1->2->3->4->5->6->7->8->NULL, K = 5 Output: 5->4->3->2->1->8
Đối với bài toán này, một phương pháp nảy ra trong đầu là duyệt danh sách và đảo ngược khi kích thước danh sách con đạt k và tiếp tục.
Phương pháp tìm giải pháp
Trong phương pháp này, ta sẽ tổng quát duyệt qua danh sách và giữ một bộ đếm để đếm số phần tử trong danh sách con. Khi bộ đếm đạt k, ta đảo ngược phần đó.
Ví dụ
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* reverse(Node* head, int k) { if (!head) return NULL; Node* curr = head; Node* next = NULL; Node* prev = NULL; int count = 0; while (curr != NULL && count < k) { // đảo ngược danh sách cho đến khi count nhỏ hơn k next = curr->next; curr->next = prev; prev = curr; curr = next; count++; } if (next != NULL) // nếu danh sách chưa kết thúc, gọi lại hàm reverse head->next = reverse(next, k); return prev; } void push(Node** head_ref, int new_data) { // hàm đẩy dữ liệu vào danh sách Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node) { // hàm in danh sách liên kết while (node != NULL) { cout << node->data << " "; node = node->next; } cout << "\n"; } int main() { Node* head = NULL; int k = 3; // k cho trước push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Original list \n"; printList(head); head = reverse(head, k); // hàm này trả về head mới cout << "New list \n"; printList(head); return (0); }Kết quả
Original list 1 2 3 4 5 6 7 8 New list 3 2 1 6 5 4 8 7
Phương pháp trên có độ phức tạp thời gian O(N), N là kích thước danh sách cho trước, và phương pháp này hoạt động bằng đệ quy. Phương pháp này có thể hoạt động với các ràng buộc lớn hơn.
Giải thích mã trên
Trong phương pháp này, ta duyệt qua mảng và đảo ngược cho đến khi biến đếm nhỏ hơn k. Khi bộ đếm đạt giá trị k, ta gọi hàm đảo ngược khác để nối nút cuối của danh sách con này đến nút đầu của danh sách con đảo ngược tiếp theo. Việc này được thực hiện bằng đệ quy.
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 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 (Bình thường) để 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.