JavaScript program deletes nodes with greater values ​​on the right

We will implement a function to delete the node with a larger value on the right side of the linked list. The method is to traverse the linked list from right to left and keep track of the maximum value encountered so far. For each node, we compare its value with the maximum value and delete the node if its value is less than the maximum value. In this way, all nodes on the right that are larger than the maximum value will be deleted.

method

The method of deleting nodes with larger values ​​on the right can be divided into the following 7 steps:

• Traverse the linked list from beginning to end.

• Keep track of the current node, the previous node, and the maximum value seen so far.

• If the value of the current node is less than the maximum value seen so far, delete the current node by updating the next pointer of the previous node.

• Update the maximum value currently seen to the value of the current node.

• Move the current node to the next node.

• Repeat steps 3 to 5 until you reach the end of the linked list.

• Return the head of the updated linked list.

Example

Given a singly linked list, the task is to delete the node with a larger value on the right. The idea is to iterate through the list from right to left and keep track of the maximum value seen so far. As we iterate through the list, we remove nodes with values ​​less than the maximum value seen so far.

This is the implementation 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;
}

illustrate

• First, we create a linked list class, which contains the Node class to define each node in the linked list.

• In the LinkedList class, we have a function add() to add new nodes to the list.

• deleteNodes()The function implements the logic of deleting the node with a larger value on the right.

• We traverse the list from right to left, keeping track of the maximum value seen so far.

• If the value of the current node is greater than the maximum value, we update the maximum value.

• If the current node's value is less than the maximum value, we delete the node by updating the previous node's next reference to point to the node next to the current node.

• Finally, if the value of the first node is less than the maximum value, we update the header reference to point to the node next to the first node.

• The linked list after deleting the node will only contain nodes with the following values:

The above is the detailed content of JavaScript program deletes nodes with greater values ​​on the right. For more information, please follow other related articles on the PHP Chinese website!