从单链表中删除元素（JavaScript）

Question

我是一个可以翻译文本的助手。以下是涉及 IT 技术的内容。您需要从单链表中移除值为 k 的元素，这是一道 CodeFights 问题。以下是我所拥有的代码（其中 l 表示列表，k 表示值）：

function removeKFromList(l, k) {
    //figure out the head of the new list so we can reference it later
    var head = l;

    while (head.value === k){
        head = head.next;
    }

    var node = head;
    var temp = null;

    while (node && node !== null) {
        if (node.next.value === k){
            temp = node.next.next;
            node.next.next = null;
            node.next = temp;
        }
        node = node.next; 
        console.log("+++", head)
    }

    console.log("---", head)  
}

CodeFight测试用例是3 -> 1 -> 2 -> 3 -> 4 -> 5。最终的结果应该是1 -> 2 -> 4 -> 5。但是我的'---'控制台日志不断返回“Empty”（根据CodeFights控制台）。每次循环时，我的'+++'控制台日志都返回正确的头元素。我一直在为此苦恼，有什么遗漏吗？

- Kaisin Li

---

请提供列表的示例以及带有值的函数调用。 - Nina Scholz

我已经包含了测试用例。该列表已经作为SLL给出，因此我不需要创建一个。希望这可以帮助。 - Kaisin Li

一个问题是第一个节点，你需要将下一个节点分配为列表的起始点。这仅适用于通过对象提供列表的情况。 - Nina Scholz

你的while循环条件应该是 while (node && node.next != null)。 - David G

Answer 1

如果您删除第一个节点，则需要返回列表。

然后，您需要使用循环来获取下一个未找到值的节点。

最后，您需要检查最后一个节点是否存在，以及是否找到该值，然后将下一个节点分配给最后一个next属性。

function removeNode(list, value) {
    var node = list,
        last;

    if (node && node.value === value) {
        return node.next;
    }

    while (node && node.value !== value) {
        last = node,
        node = node.next;
    }
    if (last && node.value === value) {
        last.next = node.next;
    }
    return list;
}

var list = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: { value: 5, next: { value: 6, next: { value: 7, next: null } } } } } } };

list = removeNode(list, 5);
console.log(list)

list = removeNode(list, 1);
console.log(list)

list = removeNode(list, 7);
console.log(list)

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

你能解释一下为什么你将“list”作为输出返回吗？我没有看到你在任何地方使用它；这是怎么工作的？ - Frog Tuna

@FrogTuna，如果你删除第一个节点，这是必要的。如果你在不重新分配的情况下使用list，你会保留该列表。如果你将赋值移入函数中，你会创建一个新的对象引用，但在外部，你仍然保留原有的引用。请参见编辑以了解区别。 - Nina Scholz

@ Nina Scholz，抱歉，我一直在尝试理解您所说的并进行自己的测试，但我仍然不明白为什么当您只调用“last.next = node.next;”时节点会从“list”中删除？这似乎意味着“last.next”中的任何更改都将传递到“list.next”中？我可以理解第一个“if语句”和第二个“while语句”，除了最后一个。 - Frog Tuna

你有没有尝试过不用它？ - Nina Scholz

@ Nina Scholz，抱歉，我误解了值类型和引用类型之间的区别，现在我完全明白你的意思了。谢谢。 - Frog Tuna

Answer 2

易于理解的解决方案：

remove(index) { 
if (index < 0 || index > this.length) return undefined 
if (index === 0) return this.shift() 
if (index === this.length - 1) return this.pop() 
let previousNode = this.get(index - 1) 
let removed = previousNode.next 
previousNode.next = removed.next 
previousNode.next = currentNode.next    
this.length-- 
return removed 
} 

get(index) { 
if (index < 0 || index >= this.length) return null 
let current = this.head 
let count = 0 
while (count !== index) { 
current = current.next 
count++ 
} 
return current 
} 

pop() { 
if (!this.head) return undefined 
let current = this.head 
let newTail = current
while (current.next) { 
newTail = current 
current = current.next 
} 
this.tail = newTail 
this.tail.next = null 
this.length-- 
if (this.length === 0) { 
this.head = null 
this.tail = null 
} 
return current 
} 
 

shift() { 
if (!this.head) return undefined 
let currentHead = this.head 
this.head = current.next 
this.length-- 
if (this.length === 0) { 
this.tail = null 
} 

return currentHead 

} 

- Vijaya Bhaskar Eswaran

Answer 3

试试这个：

function myRemove(l, k){
    if(l == null){
        return l;
    }
    while(l.value == k){
        l = l.next;
    }
    thisNode = l;
    nextNode = thisNode.next;
    while(nextNode != null){
        if(nextNode.value == k){
            thisNode.next = nextNode.next;
            // No more nodes, ie last node was to be removed
            if(thisNode.next == null)
                break;
        }
        thisNode = thisNode.next;
        nextNode = thisNode.next;       
    }
    return l;
}

- Nilesh Kevlani

Answer 4

这也可以通过递归来完成：

 function removeKFromList({value, next}, k) {       
   if(value === k){
      return next ? removeKFromList(next, k) : null;
   } else {
      return {
        next : removeKFromList(next, k),
        value
       };
  }
 }

- Jonas Wilms

---

第二个递归调用缺少第二个参数。 - Scott Sauyet