इस ट्यूटोरियल में, हमें लंबाई N की एक लिंक्ड लिस्ट A और एक पूर्णांक K दिया गया है। हमें प्रत्येक जोड़ी के आकार के साथ K के रूप में नोड्स के वैकल्पिक जोड़े को उलटना होगा। यह भी दिया गया है कि N, K से विभाज्य है। पहला तर्क है लिंक की गई सूची A का हेड पॉइंटर और दूसरा तर्क एक पूर्णांक K है, उदाहरण के लिए
इनपुट
5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2
आउटपुट
6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3
आउटपुट
5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null
समाधान खोजने के लिए दृष्टिकोण
पुनरावर्ती समाधान
-
प्रति पुनरावृत्ति (या लूप) 2K नोड्स को ट्रैवर्स करें और दिए गए इनपुट (लिंक्ड सूची) में जॉइन और टेल पॉइंटर का उपयोग करके K नोड्स के प्रत्येक जोड़े के सिर और पूंछ को रिकॉर्ड करें।
-
फिर, लिंक की गई सूची के k नोड्स को उल्टा करें और उलटी सूची के टेल नोड में शामिल हों, प्रारंभिक लिंक्ड सूची के हेड नोड के साथ, जॉइन पॉइंटर द्वारा इंगित करें।
-
फिर हम वर्तमान पॉइंटर को अगले k नोड्स में बदल देंगे।
-
सामान्य सूची की पूंछ अब अंतिम नोड के रूप में कार्य करती है (जो नई पूंछ द्वारा इंगित की जाती है), और जुड़ने वाला सूचक नई (उलट) सूची के शीर्ष पर इंगित करेगा, और वे विलय हो जाएंगे। हम इन चरणों को तब तक दोहराएंगे जब तक कि सभी नोड समान चरणों का पालन न करें।
उदाहरण
#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);
} आउटपुट
Given linked list 24 21 18 15 12 9 6 Modified Linked list 18 21 24 15 12 9 6
पुनरावर्ती समाधान
-
प्रारंभ से K नोड्स को ट्रैवर्स करें और अस्थायी मान को k+1वें नोड पर सेट करें
-
ट्रैवर्स किए गए सभी K नोड्स को उलट दें।
-
K नोड्स की उस जोड़ी के अंतिम नोड के अगले पॉइंटर को अस्थायी पर सेट करें।
-
अगले पुनरावृत्ति को छोड़ दें जिसमें उन K नोड्स की जोड़ी को छोड़ना होगा।
-
अंतिम नोड तक पहुंचने तक अगले k नोड्स को उलटने के लिए इन सभी चरणों का पुनरावर्ती रूप से पालन करें।
छद्म कोड
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
उदाहरण
#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);
} आउटपुट
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 नोड्स को रिवर्स किया जाए और c++ कोड में स्यूडो-कोड इम्प्लीमेंटेशन किया जाए। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। इस दृष्टिकोण में, हमने वैकल्पिक K नोड्स को उलटने और शेष नोड्स को छोड़ने के लिए रिकर्सन का उपयोग किया। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।