लिंक्ड लिस्ट के प्रत्येक K-वें नोड को हटाना

इस लेख में, हम लिंक्ड लिस्ट के प्रत्येक k-वें नोड को हटाने का तरीका बताएंगे। हमें उस प्रत्येक नोड को डिलीट करना होगा जो k के गुणक पर स्थित है, यानी हमें k, 2*k, 3*k, आदि स्थितियों पर नोड को डिलीट करना होगा।

इनपुट: 112->231->31->41->54->63->71->85, k = 3
आउटपुट: 112->231->41->54->71->85
व्याख्या: चूंकि 3, k-वां नोड है, इसके डिलीशन के बाद लिस्ट होगी:
पहला पुनरावृत्ति: 112->231->41->54->63->71->85
अब हम 41 से गिनते हैं, अगला k-वां नोड 63 है
दूसरे पुनरावृत्ति के बाद हमारी लिस्ट बनेगी: 112->231->41->54->71->85
और हमारा पुनरावृत्ति इसी तरह जारी रहता है।

इनपुट: 14->21->23->54->56->61, k = 1
आउटपुट: खाली लिस्ट
व्याख्या: सभी नोड्स को डिलीट करने की आवश्यकता है

इस समस्या में, हम एक सामान्य दृष्टिकोण लागू करेंगे जो पर्याप्त रूप से कुशल है ताकि हमें इसे ऑप्टिमाइज़ करने की आवश्यकता न हो।

समाधान खोजने का दृष्टिकोण

इस समस्या में, हम एक काउंटर के साथ लिंक्ड लिस्ट को पार करने जा रहे हैं। यदि काउंटर k पर पहुंचता है, तो हम उस नोड को डिलीट कर देते हैं और वर्तमान नोड से k-वें स्थान पर अगले तत्व को खोजने के लिए काउंटर को रीफ्रेश करते हैं।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

/* लिंक्ड लिस्ट नोड */
struct Node {
   int data;
   struct Node* next;
};

void push(struct Node** ref, int new_data) {
   // लिस्ट में डेटा डालना
   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}

void deletek(Node* prev, Node* curr) {
   // डिलीट फ़ंक्शन
   if (prev == NULL) {
      prev = curr;
      curr = curr->next;
      free(prev);
      prev = NULL;
   } else {
      prev->next = curr->next;
      auto tmp = curr;
      free(tmp); // स्पेस फ्री करना
   }
}

/* लिंक्ड लिस्ट प्रिंट करने के लिए फ़ंक्शन */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout << temp->data << " ";
      temp = temp->next;
   }
}

// नया नोड बनाने के लिए फ़ंक्शन
struct Node *newNode(int x) {
   Node *temp = new Node;
   temp->data = x;
   temp->next = NULL;
   return temp;
}

int main() {
   struct Node* head = NULL;
   push(&head, 80);
   push(&head, 70);
   push(&head, 60);
   push(&head, 50);
   push(&head, 40);
   push(&head, 30);
   push(&head, 20);
   
   int k = 3; // दिया गया k
   Node* curr = head; // वर्तमान पॉइंटर
   Node* prev = NULL; // पिछला पॉइंटर
   int count = 1; // स्थिति काउंटर
   
   if (head == NULL || k == 0) // यदि लिस्ट पहले से खाली है या k = 0
      cout << "अमान्य\n";
   else {
      while (curr) { // लिस्ट को पार करना
         if (count == k) {
            deletek(prev, curr);
            curr = prev->next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr->next;
         }
      }
      displayList(head); // नई लिस्ट प्रिंट करना
   }
   return 0;
}

आउटपुट

20 30 50 60 80

उपरोक्त दृष्टिकोण की समय जटिलता O(N) है, जहां N हमारी दी गई लिंक्ड लिस्ट का आकार है।

उपरोक्त कोड की व्याख्या

उपरोक्त दृष्टिकोण में, हम तीन चीजें हाथ में रखते हैं: पहला, वर्तमान पॉइंटर, दूसरा पिछला पॉइंटर, और तीसरा स्थिति काउंटर। अब जब हमारा स्थिति काउंटर k के बराबर हो जाता है तो हम कुछ नोड को डिलीट करते हैं, हम पिछले और वर्तमान काउंटर को पैरामीटर्स के रूप में डिलीट फ़ंक्शन को कॉल करते हैं, अब हम वर्तमान नोड को डिलीट करते हैं और स्पेस फ्री करते हैं, अब जब डिलीट फ़ंक्शन हो जाता है तो हम वर्तमान पॉइंटर को अगले तत्व पर शिफ्ट करते हैं और अपने काउंटर को 1 पर रीफ्रेश करते हैं और इस ब्लॉक को तब तक लूप करते हैं जब तक हमारा वर्तमान NULL नहीं हो जाता।

निष्कर्ष

इस लेख में, हम लिंक्ड लिस्ट के प्रत्येक k-वें नोड को हटाने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और पूरा दृष्टिकोण (सामान्य) भी सीखा जिसके द्वारा हमने इस समस्या को हल किया। हम इसी प्रोग्राम को अन्य भाषाओं जैसे C, Java, Python, आदि में लिख सकते हैं। आशा है कि आपको यह लेख उपयोगी लगा।