इस लेख में, हम एक एकल लिंक की गई सूची से निपटते हैं, और कार्य सूची को k के समूहों में उलटना है। उदाहरण के लिए -
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
इस समस्या के लिए, एक दृष्टिकोण जो दिमाग में आता है वह सूची से पीछे है और सूची को उलट देता है जब हमारे उपन्यास का आकार k तक पहुंच जाता है और जारी रहता है।
समाधान खोजने के लिए दृष्टिकोण
इस दृष्टिकोण में, हम आम तौर पर सूची के माध्यम से आगे बढ़ेंगे और हमारी उप-सूची में तत्वों की संख्या की गणना करने के लिए एक काउंटर रखेंगे। जब काउंटर k की गिनती तक पहुँच जाता है, तो हम उस हिस्से को उलट देते हैं।
उदाहरण
#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);
} आउटपुट
Original list 1 2 3 4 5 6 7 8 New list 3 2 1 6 5 4 8 7
उपरोक्त दृष्टिकोण में O(N) . की समय जटिलता है , जहां एन हमारी दी गई सूची का आकार है, और यह दृष्टिकोण रिकर्सन पर काम करता है। यह दृष्टिकोण उच्च बाधाओं के लिए भी काम कर सकता है।
उपरोक्त कोड की व्याख्या
हम इस दृष्टिकोण में सरणी के माध्यम से आगे बढ़ेंगे और इसे तब तक उलटते रहेंगे जब तक कि हमारा काउंटर वैरिएबल k से कम न हो जाए। जब हमारा काउंटर k के मान तक पहुँच जाता है, तो हम इस उप-सूची के अंतिम नोड को अगली उलटी उप-सूची के पहले नोड से जोड़ने के लिए एक और रिवर्सिंग फ़ंक्शन को कॉल करते हैं। यह रिकर्सन द्वारा किया जा रहा है।
निष्कर्ष
इस लेख में, हम रिकर्सन का उपयोग करके दिए गए आकार के समूहों में एक लिंक्ड सूची को उलटने के लिए एक समस्या का समाधान करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और संपूर्ण दृष्टिकोण (Normal) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम उसी प्रोग्राम को अन्य भाषाओं जैसे सी, जावा, पायथन और अन्य भाषाओं में लिख सकते हैं। हमें उम्मीद है कि आपको यह लेख मददगार लगा होगा।