Trong hướng dẫn này, chúng ta được cho một danh sách liên kết A có độ dài N và một số nguyên K. Chúng ta phải đảo ngược các cặp nút luân phiên với kích thước của mỗi cặp là K. Cũng đã cho rằng N chia hết cho K. Tham số đầu tiên là con trỏ head của danh sách liên kết A và tham số thứ hai là số nguyên K, ví dụ:
Đầu vào
5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2
Đầu ra
6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3
Đầu ra
5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null
Cách tiếp cận để tìm giải pháp
Giải pháp lặp
Duyệt 2K nút mỗi lần lặp (hoặc vòng lặp) và ghi lại head và tail của mỗi cặp K nút trong đầu vào cho trước (Danh sách liên kết) sử dụng con trỏ join và tail.
Sau đó, đảo ngược K nút của danh sách liên kết và nối nút tail của danh sách đã đảo ngược, với nút head của danh sách liên kết ban đầu, được trỏ bởi con trỏ join.
Sau đó chúng ta sẽ thay đổi con trỏ current sang K nút tiếp theo.
Tail của danh sách bình thường giờ đóng vai trò là nút cuối cùng (được trỏ bởi new tail mới), và con trỏ join sẽ trỏ đến head của danh sách mới (đã đảo ngược), và chúng được hợp nhất. Chúng ta sẽ lặp lại các bước này cho đến khi tất cả các nút tuân theo cùng các bước.
Ví dụ
#include <bits/stdc++.h> using namespace std; class Node { public: int data; Node* next; }; Node* kAltReverse(struct Node* head, int k){ Node* prev = NULL; Node* curr = head; Node* temp = NULL; Node* tail = NULL; Node* newHead = NULL; Node* join = NULL; int t = 0; while (curr) { t = k; join = curr; prev = NULL; while (curr && t--) { temp = curr->next; curr->next = prev; prev = curr; curr = temp; } if (!newHead) newHead = prev; if (tail) tail->next = prev; tail = join; tail->next = curr; t = k; while (curr && t--) { prev = curr; curr = curr->next; } tail = prev; } return newHead; } void push(Node** head_ref, int new_data){ Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printList(Node* node){ int count = 0; while (node != NULL) { cout << node->data << " "; node = node->next; count++; } } int main(void){ Node* head = NULL; int i; for (i = 6; i <27; i+=3) push(&head, i); int k = 3; cout << "Danh sách liên kết cho trước \n"; printList(head); head = kAltReverse(head, k); cout << "\n Danh sách liên kết đã sửa đổi \n"; printList(head); return (0); }Đầu ra
Danh sách liên kết cho trước 24 21 18 15 12 9 6 Danh sách liên kết đã sửa đổi 18 21 24 15 12 9 6
Giải pháp Đệ quy
Duyệt K nút từ đầu và đặt giá trị temp thành nút k+1
Đảo ngược tất cả K nút đã duyệt.
Bỏ qua vòng lặp tiếp theo nơi cặp K nút đó cần bỏ qua.
Đệ quy làm theo tất cả các bước này để đảo ngược K nút tiếp theo cho đến khi đến nút cuối cùng.
Đặt con trỏ next của nút cuối cùng của cặp K nút đó thành temp.
Mã giả
reverseAltK(head, k) curr = head prev = null next = null count = 0 WHILE count < k AND curr next = curr.next curr.next = prev prev = curr curr = next count = count + 1 IF head head.next = curr count = 0 WHILE count < k-1 AND curr curr = curr.next count = count + 1 IF curr curr.next = reverseKGroupAltRecursive(curr.next, k) return prev
Ví dụ
#include <bits/stdc++.h> using namespace std; /* Nút danh sách liên kết */ class node{ public: int data; node* next; }; /* Hàm hỗ trợ cho kAltReverse() */ node * _kAltReverse(node *node, int k, bool b); /* Đảo ngược luân phiên danh sách liên kết cho trước theo nhóm kích thước k. */ node *kAltReverse(node *head, int k){ return _kAltReverse(head, k, true); } /* Hàm hỗ trợ cho kAltReverse(). Nó đảo ngược k nút của danh sách chỉ nếu tham số thứ ba b được truyền là true, ngược lại di chuyển con trỏ k nút về phía trước và gọi đệ quy chính nó */ node * _kAltReverse(node *Node, int k, bool b){ if(Node == NULL) return NULL; int count = 1; node *prev = NULL; node *current = Node; node *next; /* Vòng lặp phục vụ hai mục đích 1) Nếu b là true, thì nó đảo ngược k nút 2) Nếu b là false, thì nó di chuyển con trỏ current */ while(current != NULL && count <= k){ next = current->next; /* Chỉ đảo ngược nút nếu b là true*/ if(b == true) current->next = prev; prev = current; current = next; count++; } /* 3) Nếu b là true, thì node là nút thứ k. Vì vậy gắn phần còn lại của danh sách sau node. 4) Sau khi gắn, trả về head mới */ if(b == true){ Node->next = _kAltReverse(current, k, !b); return prev; } /* Nếu b không true, thì gắn phần còn lại của danh sách sau prev. Vì vậy gắn phần còn lại của danh sách sau prev */ else{ prev->next = _kAltReverse(current, k, !b); return Node; } } /* CÁC HÀM TIỆN ÍCH */ /* Hàm đẩy một nút */ void push(node** head_ref, int new_data){ /* cấp phát nút */ node* new_node = new node(); /* đặt dữ liệu */ new_node->data = new_data; /* liên kết danh sách cũ từ nút mới */ new_node->next = (*head_ref); /* di chuyển head để trỏ đến nút mới */ (*head_ref) = new_node; } /* Hàm in danh sách liên kết */ void printList(node *node){ int count = 0; while(node != NULL){ cout << node->data << " "; node = node->next; count++; } } // Driver Code int main(void){ /* Bắt đầu với danh sách rỗng */ node* head = NULL; int i; // tạo danh sách 1->2->3->4->5...... ->20 for(i = 20; i > 0; i--) push(&head, i); cout << "Danh sách liên kết cho trước \n"; printList(head); head = kAltReverse(head, 3); cout << "\nDanh sách liên kết đã sửa đổi \n"; printList(head); return(0); }Đầu ra
Danh sách liên kết cho trước 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Danh sách liên kết đã sửa đổi 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
Kết luận
Hướng dẫn này đã dạy chúng ta cách đảo ngược K nút luân phiên trong danh sách liên kết đơn và triển khai mã giả trong code C++. Chúng ta cũng có thể viết code này bằng Java, Python và các ngôn ngữ khác. Trong cách tiếp cận này, chúng ta sử dụng đệ quy để đảo ngược K nút luân phiên và bỏ qua các nút còn lại. Hy vọng bạn thấy hướng dẫn này hữu ích.