Trong bài viết này, chúng ta giải quyết một danh sách được liên kết đơn lẻ và nhiệm vụ là đảo ngược danh sách theo nhóm 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 vấn đề này, một phương pháp được nghĩ đến là theo dõi danh sách và đảo ngược danh sách khi kích thước danh sách phụ của chúng tôi đạt đến k và tiếp tục.
Phương pháp tiếp cận để tìm ra giải pháp
Trong cách tiếp cận này, chúng ta thường sẽ duyệt qua danh sách và giữ một bộ đếm để đếm số phần tử trong danh sách con của chúng ta. Khi bộ đếm đạt đến số đếm k, chúng tôi đả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) { // we reverse the list till our count is less than k
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (next != NULL) // if our link list has not ended we call reverse function again
head->next = reverse(next, k);
return prev;
}
void push(Node** head_ref, int new_data) { // function for pushing data in the list
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node) { // function to print linked list
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << "\n";
}
int main() {
Node* head = NULL;
int k = 3; // the given k
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); // this function will return us our new head
cout << "New list \n";
printList(head);
return (0);
} Đầu ra
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 về thời gian là O (N) , trong đó N là kích thước của danh sách đã cho của chúng tôi và cách tiếp cận này hoạt động trên đệ quy. Cách tiếp cận này cũng có thể hoạt động đối với các ràng buộc cao hơn.
Giải thích về đoạn mã trên
Chúng ta sẽ duyệt qua mảng trong cách tiếp cận này và tiếp tục đảo ngược nó cho đến khi biến bộ đếm của chúng ta nhỏ hơn k. Khi bộ đếm của chúng ta đạt đến giá trị k, chúng ta gọi một hàm đảo ngược khác để kết nối nút cuối cùng của danh sách con này với nút đầu tiên của danh sách con được đảo ngược tiếp theo. Điều này đang được thực hiện bằng đệ quy.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề Đảo ngược danh sách được liên kết trong các nhóm có kích thước nhất định bằng cách sử dụng đệ quy. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.