Le programme JavaScript supprime les nœuds avec des valeurs plus élevées à droite

Nous implémenterons une fonction pour supprimer le nœud avec une valeur plus grande sur le côté droit de la liste chaînée. La méthode consiste à parcourir la liste chaînée de droite à gauche et à garder une trace de la valeur maximale rencontrée jusqu'à présent. Pour chaque nœud, nous comparons sa valeur avec la valeur maximale et supprimons le nœud si sa valeur est inférieure à la valeur maximale. De cette façon, tous les nœuds de droite qui sont plus grands que la valeur maximale seront supprimés.

Méthode

La méthode de suppression des nœuds avec des valeurs plus grandes à droite peut être divisée en 7 étapes suivantes :

• Parcourez la liste chaînée du début à la fin.

• Gardez une trace du nœud actuel, du nœud précédent et de la valeur maximale vue jusqu'à présent.

• Si la valeur du nœud actuel est inférieure à la valeur maximale vue jusqu'à présent, supprimez le nœud actuel en mettant à jour le pointeur suivant du nœud précédent.

• Mettez à jour la valeur maximale actuellement observée avec la valeur du nœud actuel.

• Déplacez le nœud actuel vers le nœud suivant.

• Répétez les étapes 3 à 5 jusqu'à ce que vous atteigniez la fin de la liste chaînée.

• Renvoie l'en-tête de la liste chaînée mise à jour.

Exemple

Étant donné une liste à chaînage unique, la tâche consiste à supprimer le nœud ayant la plus grande valeur sur le côté droit. L'idée est de parcourir la liste de droite à gauche et de garder une trace de la valeur maximale vue jusqu'à présent. Au fur et à mesure que nous parcourons la liste, nous supprimons les nœuds dont les valeurs sont inférieures à la valeur maximale vue jusqu'à présent.

Voici l'implémentation en JavaScript -

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = null;
  }
  // Add a new node to the linked list
  add(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = node;
  }
  // Function to delete nodes with greater value on right
  deleteNodes() {
    let prev = null;
    let current = this.head;
    let max = this.head.value;
    // Traverse the linked list from right to left
    while (current.next) {
      // If the current node has a greater value than the max value seen so far
      if (current.next.value > max) {
        max = current.next.value;
        prev = current;
      } else {
        // Delete the node with smaller value
        prev.next = current.next;
      }
      current = current.next;
    }
    // If the last node has a smaller value than the max value seen so far
    if (this.head.value < max) {
      this.head = this.head.next;
    }
  }
}
// Test the code
const linkedList = new LinkedList();
linkedList.add(12);
linkedList.add(15);
linkedList.add(10);
linkedList.add(11);
linkedList.add(5);
linkedList.add(6);
linkedList.add(2);
linkedList.add(3);
linkedList.deleteNodes();
let current = linkedList.head;
while (current) {
  console.log(current.value);
  current = current.next;
}

Instructions

• Tout d'abord, nous créons une classe de liste chaînée, qui contient la classe Node pour définir chaque nœud de la liste chaînée.

• Dans la classe LinkedList, nous avons une fonction add() pour ajouter de nouveaux nœuds à la liste.

La fonction

• deleteNodes() implémente la logique de suppression des nœuds avec des valeurs plus grandes à droite.

• Nous parcourons la liste de droite à gauche, en gardant une trace de la valeur maximale vue jusqu'à présent.

• Si la valeur du nœud actuel est supérieure à la valeur maximale, nous mettons à jour la valeur maximale.

• Si la valeur du nœud actuel est inférieure à la valeur maximale, nous supprimons le nœud en mettant à jour la référence next du nœud précédent pour pointer vers le nœud à côté du nœud actuel.

• Enfin, si la valeur du premier nœud est inférieure à la valeur maximale, nous mettons à jour la référence d'en-tête pour pointer vers le nœud à côté du premier nœud.

• La liste chaînée après la suppression du nœud ne contiendra que des nœuds avec les valeurs suivantes :

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!