Trong bài toán này, chúng ta được đưa ra một con trỏ đến phần đầu của danh sách liên kết và một số nguyên k. Trong các nhóm có kích thước k, chúng ta cần đảo ngược danh sách liên kết. Ví dụ -
Input : 1 <-> 2 <-> 3 <-> 4 <-> 5 (doubly linked list), k = 3 Output : 3 <-> 2 <-> 1 <-> 5 <-> 4
Phương pháp tiếp cận để tìm ra giải pháp
Trong bài toán này, chúng ta sẽ thực hiện một thuật toán đệ quy để giải quyết vấn đề này. Trong cách tiếp cận này, chúng tôi sẽ sử dụng đệ quy và giải quyết vấn đề bằng cách sử dụng đó.
Ví dụ
#include <iostream>
using namespace std;
struct Node {
int data;
Node *next, *prev;
};
// push function to push a node into the list
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) { // going to the last node
TMP = TMP->next;
}
TMP->next = new_node;
new_node->prev = TMP;
return head; // return pointer to head
}
// function to print given list
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) { // while our count is less than k we simply reverse the nodes.
newHead = CURRENT;
TMP = CURRENT->prev;
CURRENT->prev = CURRENT->next;
CURRENT->next = TMP;
CURRENT = CURRENT->prev;
count++;
}
if (count >= k) {
head->next = revK(CURRENT, k); // now when if the count is greater or equal
//to k we connect first head to next head
}
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);
}
Đầu ra
Original List : 1 2 3 4 5 Modified List : 3 2 1 5 4
Giải thích về đoạn mã trên
Trong cách tiếp cận này, chúng ta đang duyệt qua danh sách và duyệt qua cho đến khi số lượng của chúng ta nhỏ hơn k. Chúng tôi thực hiện và gọi đệ quy đưa giá trị đó vào head -> next (ở đây chúng tôi chỉ đơn giản là đảo ngược danh sách khi chúng tôi đi qua, nhưng khi đạt đến k của chúng tôi, chúng tôi cần phải làm cho đầu của chúng tôi trỏ đến một danh sách khác phần tử thứ k, nếu danh sách là 1 2 3 4 5 và k của chúng ta là 3, trong đó chúng ta đảo ngược các phần tử ở giữa thành 3 2 1 nhưng bây giờ chúng ta cần 1 của chúng ta trỏ thành 4 vì phần tử đó cũng sẽ được đảo ngược, vì vậy đó là lý do tại sao chúng ta sử dụng gọi đệ quy và thực hiện thêm một câu lệnh if.).
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 kép 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 mà chúng tôi đã giải quyết. 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.