Trong hướng dẫn này, chúng ta được cung cấp 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 thay thế 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. Đối số đầu tiên là con trỏ đầu của danh sách được liên kết A và đối số thứ hai là số nguyên K, chẳng hạn
Đầ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
Phương pháp tiếp cận để tìm giải pháp
Giải pháp lặp lại
-
Duyệt qua 2K nút mỗi lần lặp (hoặc vòng lặp) và ghi lại phần đầu và phần đuôi của mỗi cặp nút K trong đầu vào đã cho (Danh sách được liên kết) bằng cách sử dụng con trỏ nối và con trỏ đuôi.
-
Sau đó, đảo ngược k nút của danh sách được liên kết và nối nút đuôi của danh sách đã đảo ngược, với nút đầu của danh sách được liên kết ban đầu, được trỏ bởi con trỏ tham gia.
-
Sau đó, chúng tôi sẽ thay đổi con trỏ hiện tại thành k nút tiếp theo.
-
Phần đuôi của danh sách bình thường bây giờ đóng vai trò là nút cuối cùng (được trỏ bởi phần đuôi mới) và con trỏ nối sẽ trỏ đến phần đầu của danh sách mới (đã đảo ngược) và chúng được hợp nhất. Chúng tôi sẽ lặp lại các bước này cho đến khi tất cả các nút thực hiện theo các bước tương tự.
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 << "Given linked list \n";
printList(head);
head = kAltReverse(head, k);
cout << "\n Modified Linked list \n";
printList(head);
return (0);
} Đầu ra
Given linked list 24 21 18 15 12 9 6 Modified Linked list 18 21 24 15 12 9 6
Giải pháp đệ quy
-
Di chuyển qua K nút từ điểm bắt đầu và đặt giá trị tạm thời thành nút thứ k + 1
-
Đảo ngược tất cả các nút K đã duyệt qua.
-
Đặt con trỏ tiếp theo của nút cuối cùng của cặp K nút đó thành tạm thời.
-
Bỏ qua bước lặp tiếp theo mà cặp K nút đó cần bỏ qua.
-
Làm theo đệ quy tất cả các bước này để đảo ngược k nút tiếp theo cho đến khi đạt đến nút cuối cùng.
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;
/* Link list node */
class node{
public:
int data;
node* next;
};
/* Helper function for kAltReverse() */
node * _kAltReverse(node *node, int k, bool b);
/* Alternatively reverses the given linked list
in groups of given size k. */
node *kAltReverse(node *head, int k){
return _kAltReverse(head, k, true);
}
/* Helper function for kAltReverse().
It reverses k nodes of the list only if
the third parameter b is passed as true,
otherwise moves the pointer k nodes ahead
and recursively calls iteself */
node * _kAltReverse(node *Node, int k, bool b){
if(Node == NULL)
return NULL;
int count = 1;
node *prev = NULL;
node *current = Node;
node *next;
/* The loop serves two purposes
1) If b is true,
then it reverses the k nodes
2) If b is false,
then it moves the current pointer */
while(current != NULL && count <= k){
next = current->next;
/* Reverse the nodes only if b is true*/
if(b == true)
current->next = prev;
prev = current;
current = next;
count++;
}
/* 3) If b is true, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head */
if(b == true){
Node->next = _kAltReverse(current, k, !b);
return prev;
}
/* If b is not true, then attach
rest of the list after prev.
So attach rest of the list after prev */
else{
prev->next = _kAltReverse(current, k, !b);
return Node;
}
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(node** head_ref, int new_data){
/* allocate node */
node* new_node = new node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(node *node){
int count = 0;
while(node != NULL){
cout << node->data << " ";
node = node->next;
count++;
}
}
// Driver Code
int main(void){
/* Start with the empty list */
node* head = NULL;
int i;
// create a list 1->2->3->4->5...... ->20
for(i = 20; i > 0; i--)
push(&head, i);
cout << "Given linked list \n";
printList(head);
head = kAltReverse(head, 3);
cout << "\nModified Linked list \n";
printList(head);
return(0);
} Đầu ra
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 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 thay thế trong một danh sách được liên kết đơn lẻ và triển khai mã giả trong mã c ++. Chúng tôi cũng có thể viết mã 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 tôi sử dụng đệ quy để đảo ngược K nút thay thế và bỏ qua các nút còn lại. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.