链表 - 跟踪每个节点

Question

我找到了一种算法来遍历排序的链表并删除重复项。我写的，有效。

不过，我还是不明白这是怎么回事。在循环的最后，为了进入 while 循环，我们这样做：

currentNode = nextNode

这怎么能不擦除当前节点呢？为什么链表还在这里？感觉每个节点每次都被下一个节点擦除，不是吗？

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

function removeDuplicatesFromLinkedList(linkedList) {
    let currentNode = linkedList;

while(currentNode !== null){
    let nextNode = currentNode.next;
    
    while(nextNode !== null && nextNode.value === currentNode.value){
        nextNode = nextNode.next;
    }
    
    currentNode.next = nextNode
    currentNode= nextNode
    
}
currentNode = linkedList;

return linkedList;

}

exports.LinkedList = LinkedList;
exports.removeDuplicatesFromLinkedList = removeDuplicatesFromLinkedList;

Answer 1

事实上，linkedList永远不会被覆盖，所以初始列表没有损坏（因为删除重复项时，保留第一个，只删除以下）。

那么，currNode就是当前指针，指向当前节点。为其分配一个新值不要删除以前的节点，因为它仍然通过列表头引用 linkedList.

真正缺少的是删除节点上的 free 指令 - 该算法依赖于垃圾收集器在没有内存泄漏的情况下工作。

Answer 2

让我们举个例子：

2 -> 3 -> 3 -> 4

最初currentNode == 2。在循环的第一次迭代中 nextNode == 3，这是当前节点的下一个节点。内部 while 循环不运行因为 currentNode.value 不等于 nextNode.value。所以我们点击：

    currentNode.next = nextNode
    currentNode= nextNode

这会将 currentNode 的下一个节点设置为 NextNode。所以，什么都没有改变。然后我们将当前节点向前移动一位：currentNode = nextNode

不过，在下一次迭代中，nextNode == 3，而 currentNode == 3 也是。现在内部 while 循环运行进行一次迭代并将 nextNode 移动到 4 并中断，因为它们不再相等。然后，currentNode.next设置为nextNode，即4，nextNode赋值后currentNode。

由于这些都是指向节点的指针，因此不会删除任何内容。只是从链接节点链中删除了重复值。

链表 - 跟踪每个节点

Linked List - Keeping track of each node

algorithm

linked-list