Das JavaScript-Programm löscht rechts Knoten mit größeren Werten

Wir werden eine Funktion implementieren, um den Knoten mit einem größeren Wert auf der rechten Seite der verknüpften Liste zu löschen. Die Methode besteht darin, die verknüpfte Liste von rechts nach links zu durchlaufen und den bisher gefundenen Maximalwert zu verfolgen. Für jeden Knoten vergleichen wir seinen Wert mit dem Maximalwert und löschen den Knoten, wenn sein Wert kleiner als der Maximalwert ist. Auf diese Weise werden alle Knoten auf der rechten Seite gelöscht, die größer als der Maximalwert sind.

Methode

Die Methode zum Löschen von Knoten mit größeren Werten auf der rechten Seite kann in die folgenden 7 Schritte unterteilt werden:

• Durchlaufen Sie die verknüpfte Liste von Anfang bis Ende.

• Verfolgen Sie den aktuellen Knoten, den vorherigen Knoten und den bisher gesehenen Maximalwert.

• Wenn der Wert des aktuellen Knotens kleiner als der bisher gesehene Maximalwert ist, löschen Sie den aktuellen Knoten, indem Sie den nächsten Zeiger des vorherigen Knotens aktualisieren.

• Aktualisieren Sie den aktuell angezeigten Maximalwert auf den Wert des aktuellen Knotens.

• Verschieben Sie den aktuellen Knoten zum nächsten Knoten.

• Wiederholen Sie die Schritte 3 bis 5, bis Sie das Ende der verknüpften Liste erreicht haben.

• Gibt den Kopf der aktualisierten verknüpften Liste zurück.

Beispiel

Bei einer einfach verknüpften Liste besteht die Aufgabe darin, den Knoten mit dem größeren Wert auf der rechten Seite zu löschen. Die Idee besteht darin, die Liste von rechts nach links zu durchlaufen und den bisher gesehenen Maximalwert im Auge zu behalten. Während wir die Liste durchlaufen, entfernen wir Knoten mit Werten, die unter dem bisher gesehenen Maximalwert liegen.

Dies ist die Implementierung in 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;
}

Anleitung

• Zuerst erstellen wir eine verknüpfte Listenklasse, die die Node-Klasse enthält, um jeden Knoten in der verknüpften Liste zu definieren.

• In der LinkedList-Klasse haben wir eine Funktion add(), um neue Knoten zur Liste hinzuzufügen.

Die Funktion

• deleteNodes() implementiert die Logik zum Löschen von Knoten mit größeren Werten auf der rechten Seite.

• Wir durchlaufen die Liste von rechts nach links und behalten dabei den bisher gesehenen Maximalwert im Auge.

• Wenn der Wert des aktuellen Knotens größer als der Maximalwert ist, aktualisieren wir den Maximalwert.

• Wenn der Wert des aktuellen Knotens kleiner als der Maximalwert ist, löschen wir den Knoten, indem wir die next-Referenz des vorherigen Knotens aktualisieren, um auf den Knoten neben dem aktuellen Knoten zu verweisen.

• Wenn schließlich der Wert des ersten Knotens kleiner als der Maximalwert ist, aktualisieren wir die Header-Referenz so, dass sie auf den Knoten neben dem ersten Knoten zeigt.

• Die verknüpfte Liste enthält nach dem Löschen des Knotens nur Knoten mit den folgenden Werten:

Das obige ist der detaillierte Inhalt vonDas JavaScript-Programm löscht rechts Knoten mit größeren Werten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!