数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript程序：删除右侧值更大的节点
我们将实现一个函数，用于删除链表中右侧值更大的节点。方法是从右到左遍历链表，并跟踪迄今为止遇到的最大值。对于每个节点，我们将它的值与最大值进行比较，如果它的值小于最大值，则删除该节点。这样，所有右侧值大于其自身值的节点都将被删除。
方法
删除右侧值更大的节点的方法可以解释为以下7个步骤：
从头到尾遍历链表。
跟踪当前节点、前一个节点和迄今为止看到过的最大值。
如果当前节点的值小于迄今为止看到过的最大值，则通过更新前一个节点的下一个指针来删除当前节点。
将迄今为止看到过的最大值更新为当前节点的值。
将当前节点移动到下一个节点。
重复步骤3到5，直到到达链表的末尾。
返回更新后的链表的头节点。
示例
给定一个单链表，任务是删除右侧值更大的节点。其思想是从右到左遍历列表，并跟踪迄今为止看到过的最大值。当我们遍历列表时，我们删除其值小于迄今为止看到过的最大值节点。
以下是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;
}
解释
首先，我们创建一个链表类和一个Node类来定义列表中的每个节点。
在LinkedList类中，我们有一个add()函数用于向列表中添加新节点。
deleteNodes()函数实现了删除右侧值更大的节点的逻辑。
我们从右到左遍历列表，跟踪迄今为止看到过的最大值。
如果当前节点的值大于最大值，则更新最大值。
如果当前节点的值小于最大值，则通过更新前一个节点的next引用指向当前节点的下一个节点来删除该节点。
最后，如果第一个节点的值小于最大值，则更新头引用以指向第一个节点的下一个节点。
删除节点后，链表将只包含值……的节点
更新于：2023年3月13日
235 次浏览
广告