Supprimer les nœuds dont la valeur est supérieure à droite

Supprimer les nœuds dont la valeur est supérieure à droite

Étant donné une liste liée individuellement, supprimez tous les nœuds qui ont une plus grande valeur sur le côté droit.

Exemples:

a) La liste 12-> 15-> 10-> 11-> 5-> 6-> 2-> 3-> NULL doit être remplacée par 15-> 11-> 6-> 3-> NULL. Notez que 12, 10, 5 et 2 ont été supprimés car il existe une valeur supérieure sur le côté droit.

Lorsque nous examinons 12, nous voyons qu’après 12 il y a un nœud avec une valeur supérieure à 12 (c’est-à-dire 15), nous supprimons donc 12. Lorsque nous examinons 15, nous ne trouvons aucun nœud après 15 ayant une valeur supérieure à 15, nous le conservons nœud. Quand on y va, on a 15-> 6-> 3

b) La liste 10-> 20-> 30-> 40-> 50-> 60-> NULL doit être remplacée par 60-> NULL. Notez que 10, 20, 30, 40 et 50 ont été supprimés car ils ont tous une valeur supérieure sur le côté droit.

c) La liste 60-> 50-> 40-> 30-> 20-> 10-> NULL ne doit pas être modifiée.

J’ai écrit la fonction pour cela. Mais ça ne marche pas.

void remove_lower(struct node** head_ref) { struct node* current = (*head_ref); if(current != NULL && current->next != NULL) return ; struct node* temp; while(current->next != NULL) { if(current->data > current->next->data) { temp = current->next; current = temp->next; free(temp); } else current = current->next; } } 

Vous devez suivre l’élément “précédent” et mettre à jour son pointeur “suivant”, sinon vous cassez la liste en supprimant un élément qui ne figure pas en premier dans la liste. De plus, votre algorithme supprime tous les “prochains” éléments qui sont “plus grands” que les éléments actuels. Selon votre description, vous alliez supprimer l’élément “current” s’il contenait un élément supérieur sur son côté droit. Donc, vous devriez supprimer l’élément “courant”, pas l’élément suivant.

Je suggérerais l’approche suivante (cochée chez ideone ) pour cet algorithme (malheureusement, O(N^2) ):

 void remove_lower(struct node** head_ref) { struct node* current = (*head_ref); if(current == NULL || current->next == NULL) return ; struct node* prev = NULL, *next = NULL, *temp = NULL; while(current->next != NULL) { next = current->next; temp = next; /* check if there is any element greater than current */ while(temp->next != NULL) { if (temp->data > current->data) { /* * if some element is greater than current, then * delete current element */ free(current); current = NULL; if (prev == NULL) { /* it was the first element, need to update the head */ *head_ref = next; } else { prev->next = next; } break; } temp = temp->next; } /* if current element was not deleted */ if (current != NULL) { prev = current; } current = next; } } 

Sortie:

Des données d’entrée:

 2->7->1->36->6->0->5->-1->16->4->-2->3->-3->4->2->-4->1->-5->0->0->NULL 

Des données de sortie:

 36->16->4->4->2->1->0->0->NULL 

Vous semblez avoir inversé les conditions de vos déclarations if.

 if(current != NULL && current->next != NULL) return ; 

Changez le en:

 if (current == NULL || current->next == NULL) return ; 

Et l’autre:

  if(current->data > current->next->data) { 

changer à:

  if(current->data < current->next->data) { 

N’est-ce pas ce que vous voulez dire?

 if(current == NULL || current->next == NULL) return ; 

Algorithme Voici Mon Algorithme dont la complexité temporelle est O(n)

  1. Inverser la liste.

  2. Parcourez la liste inversée. Gardez le maximum jusqu’à maintenant. Si le noeud suivant

  3. Inversez à nouveau la liste pour conserver la commande d’origine.

     void reverseList(struct node **headref); void _delLesserNodes(struct node *head); /* Deletes nodes which have a node with greater value node on left side */ void delLesserNodes(struct node **head_ref) { /* 1) Reverse the linked list */ reverseList(head_ref); /* 2) In the reversed list, delete nodes which have a node with greater value node on left side. Note that head node is never deleted because it is the leftmost node.*/ _delLesserNodes(*head_ref); /* 3) Reverse the linked list again to retain the original order */ reverseList(head_ref); } /* Deletes nodes which have greater value node(s) on left side */ void _delLesserNodes(struct node *head) { struct node *current = head; /* Initialize max */ struct node *maxnode = head; struct node *temp; while (current != NULL && current->next != NULL) { /* If current is smaller than max, then delete current */ if(current->next->data < maxnode->data) { temp = current->next; current->next = temp->next; free(temp); } /* If current is greater than max, then update max and move current */ else { current = current->next; maxnode = current; } } } //*********************************************** void reverseList(struct node **headref) { struct node *current = *headref; struct node *prev = NULL; struct node *next; while(current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *headref = prev; } 

Faites-le moi savoir, s’il y a une erreur

  if(current != NULL && current->next != NULL) return ; 

Je pense que vous avez un problème ici. Cela se termine dans la première étape. Vous voudrez peut-être écrire

  if(current == NULL || current->next == NULL) return ; 

Il serait utile que vous nous en disiez plus sur ce qui ne fonctionne pas, par exemple les entrées et les sorties, les erreurs du compilateur ou les emstackments de débogage.

Cela dit, je vois que vous supprimez la valeur suivante si elle est inférieure à la valeur actuelle (c’est-à-dire son prédécesseur, sa “gauche”), ce qui, à mon sens, n’est pas une exigence. Ne devriez-vous pas supprimer le courant s’il est plus petit que le suivant, conformément aux exigences?

Sans renverser aussi, cela peut être fait.

Voici le code

 public void delNodes(Node n){ Node curr = n; while(curr != null && curr.next != null){ if(curr.data < curr.next.data){ Node temp = curr.next; curr.data = temp.data; curr.next = temp.next; temp = null; }else{ curr = curr.next; } } }