Löschen Sie jeden K-ten Knoten in der verknüpften Liste

In diesem Artikel erklären wir, wie man jeden k-ten Knoten in einer verknüpften Liste löscht. Wir müssen jeden Knoten löschen, der sich auf einem Vielfachen von k befindet, d. h. wir müssen Knoten an den Positionen k, 2*k, 3*k usw. löschen.

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

In diesem Problem werden wir eine triviale Methode anwenden, die effizient genug ist, sodass wir sie nicht optimieren müssen.

So finden Sie die Lösung

In diesem Problem werden wir eine verknüpfte Liste mit einem Zähler durchlaufen. Wenn der Zähler k erreicht, löschen wir den Knoten und aktualisieren den Zähler, um das nächste Element an der k-ten Position des aktuellen Knotens zu finden.

Beispiel

#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;
}

Ausgabe

20 30 50 60 80

Die zeitliche Komplexität der obigen Methode beträgt O(N), wobei N die Größe der angegebenen verknüpften Liste ist.

Erklärung des obigen Codes

In der obigen Methode behalten wir zunächst drei Dinge bei: Das erste ist der aktuelle Zeiger, das zweite ist der vorherige Zeiger und das dritte ist der Positionszähler. Wenn nun unser Positionszähler gleich k ist, löschen wir einen bestimmten Knoten, rufen die Löschfunktion auf und übergeben den vorherigen und aktuellen Zähler als Parameter. Dann löschen wir den aktuellen Knoten und geben den Platz frei. Wenn die Löschfunktion abgeschlossen ist, bewegen wir uns Setzen Sie den aktuellen Zeiger auf das nächste Element und aktualisieren Sie den Zähler auf 1, indem Sie diesen Block in einer Schleife durchlaufen, bis der aktuelle Zeiger NULL wird.

Fazit

In diesem Artikel haben wir das Problem gelöst, jeden k-ten Knoten einer verknüpften Liste zu löschen. Wir haben auch ein C++-Programm und einen vollständigen (trivialen) Ansatz zur Lösung dieses Problems gelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Ich hoffe, Sie finden diesen Artikel hilfreich.

Das obige ist der detaillierte Inhalt vonLöschen Sie jeden K-ten Knoten in der verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!