Supprimez chaque Kème nœud de la liste chaînée

Dans cet article, nous expliquerons comment supprimer chaque kème nœud d'une liste chaînée. Nous devons supprimer chaque nœud situé sur un multiple de k, c'est-à-dire que nous devons supprimer les nœuds aux positions k, 2*k, 3*k, etc.

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

Dans ce problème, nous appliquerons une méthode triviale suffisamment efficace pour ne pas avoir besoin de l'optimiser.

Comment trouver la solution

Dans ce problème, nous allons parcourir la liste chaînée avec un compteur. Si le compteur atteint k, nous supprimons le nœud et actualisons le compteur pour trouver l'élément suivant à la k-ème position du nœud actuel.

Exemple

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

Sortie

20 30 50 60 80

La complexité temporelle de la méthode ci-dessus est O(N), où N est la taille de la liste chaînée donnée.

Explication du code ci-dessus

Dans la méthode ci-dessus, nous gardons d'abord trois choses, la première est le pointeur actuel, la seconde est le pointeur précédent et la troisième est le compteur de position. Maintenant, lorsque notre compteur de position est égal à k, nous supprimons un certain nœud, appelons la fonction de suppression et passons le compteur précédent et actuel comme paramètres, puis nous supprimons le nœud actuel et libérons de l'espace, lorsque la fonction de suppression est terminée, nous nous déplaçons le pointeur actuel vers l'élément suivant et actualisez le compteur à 1, en bouclant ce bloc jusqu'à ce que le pointeur actuel devienne NULL.

Conclusion

Dans cet article, nous avons résolu le problème de la suppression de chaque kème nœud d'une liste chaînée. Nous avons également appris un programme C++ et une approche complète (triviale) pour résoudre ce problème. Nous pouvons écrire le même programme dans d'autres langages comme C, Java, Python et autres. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!