javascript - 根据值从链表中删除节点

Question

我正在解决 Hackerrank 问题，并尝试删除大于特定值的所有节点。

这是他们的基本实现

const SinglyLinkedListNode = class{
  constructor(value) {
    this.value = value;
    this.next = null;
  }
};

const SinglyLinkedList = class {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  insertNode(value) {
    const node = new SinglyLinkedListNode(value);
    if(!this.head) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    this.tail = node;
  }
};

我的删除节点函数如下...

SinglyLinkedList.prototype.removeNodes = function(listHead, x){
  let currentNode = listHead;

  while(currentNode !== null && currentNode.next !== null) {
    let next = currentNode.next;
    while (next !== null && next.value > x) {
      next = next.next
    }
    currentNode.next = next
    if(currentNode.next === null) {
      break;
    }
  }
  return currentNode
}

参数为:listhead - 根节点的引用，x - 用于过滤链表的整数值

例如，LL 是 1-> 2 -> 4 -> 3 -> 5，我需要删除所有大于 x (3) 的节点并保持 LL 顺序的完整性。结果应该是 1 -> 2 -> 3。

我很困惑为什么我一直得到 this.tail.value = 5 而不是this.tail.value = 3，this.tail.next = null。

这是一个REPL

Answer 1

因为 tail 必须显式重写，否则它会保留对未链接节点的引用。在运行该函数之前，列表如下所示:

  list: head                                   tail
           1    ->    2   ->    3  ->    4    ->  5

之后尾部仍然指向 5，尽管它没有链接:

 list: head                                  tail
         1    ->    2   ->    3             5

要解决此问题，只需重写函数末尾的尾部即可:

 return this.tail = currentNode;

此外，您还必须实际遍历列表，因此添加一个

 currentNode = currentNode.next;

在外部while的末尾。