所属分类:web前端开发
我们将实现一个函数来删除链表中右侧具有更大值的节点。方法是从右向左遍历链表并跟踪到目前为止遇到的最大值。对于每个节点,我们将其值与最大值进行比较,如果其值小于最大值则删除该节点。这样,右侧所有大于最大值的节点都会被删除。
删除右侧值较大的节点的方法可以分为以下 7 个步骤:
从头到尾遍历链表。
跟踪当前节点、前一个节点以及迄今为止看到的最大值。
如果当前节点的值小于目前看到的最大值,则通过更新前一个节点的 next 指针来删除当前节点。
将目前看到的最大值更新为当前节点的值。
将当前节点移动到下一个节点。
重复步骤 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 引用以指向当前节点的下一个节点来删除该节点。
最后,如果第一个节点的值小于最大值,我们更新头引用以指向第一个节点的下一个节点。
删除节点后的链表将只包含值为以下的节点: