लिंक की गई सूची के प्रत्येक K-वें नोड को हटा दें

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

Input : 112->231->31->41->54->63->71->85
   k = 3
Output : 112->231->41->54->71->85
Explanation: As 3 is the k-th node after its deletion list would be :
First iteration :112->231->41->54->63->71->85
Now we count from 41 the next kth node is 63
After the second iteration our list will become : 112->231->41->54->71->85
And our iteration continues like this.

Input: 14->21->23->54->56->61
   k = 1
Output: Empty list
Explanation: All nodes need to be deleted

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

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

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

उदाहरण

#include<bits/stdc++.h>
using namespace std;
/* Linked list Node */
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the data into the list

   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
void deletek(Node* prev, Node* curr) { // delete function

   if(prev == NULL) {
      prev = curr;
      curr = curr -> next;
      free(prev);
      prev = NULL;
   } else {
      prev -> next = curr -> next;
      auto tmp = curr;
      free(tmp); // freeing the space
   }
}
/* Function to print linked list */
void displayList(struct Node *head) {
   struct Node *temp = head;
   while (temp != NULL) {
      cout<<temp->data<<" ";
      temp = temp->next;
   }
}
// Function to create a new node.
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; // given k
   Node* curr = head; // current pointer
   Node* prev = NULL; // previous pointer
   int count = 1; // position counter
   if(head == NULL || k == 0) // if list is already empty or k = 0
      cout << "Invalid\n";
   else {
      while(curr) { // traversing the list
         if(count == k) {
            deletek(prev, curr);
            curr = prev -> next;
            count = 1;
         } else {
            count++;
            prev = curr;
            curr = curr -> next;
         }
      }
      displayList(head); // printing the new list
   }
   return 0;
}

आउटपुट

20 30 50 60 80

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

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

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

निष्कर्ष

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