algorithm - O(1) 复杂度删除单个链表中一个元素的算法

Question

我是德国计算机专业的学生。我的教授给出了以下问题来思考：

'给定对单个链表中节点的引用（不是最后一个节点）。给出一个算法从列表中删除这个元素，它具有 O(1) 复杂度，同时保持完整性。

我想过这个，但我很确定，没有这样的算法。因为它是一个单链表，你必须遍历链表中的每个节点，直到你到达应该删除的节点，因为你必须在删除之前修改节点中的下一个指针。这将导致 O(n) 复杂度。

我错过了什么吗？

Answer 1

这取决于节点是否可变（值）。

有一种方法可以做到这一点，如果你可以对节点做你喜欢的事情：

toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next

现在所有的信息toDelete都被旧的信息覆盖了toDelete.next。（根据平台，您可能需要释放旧的toDelete.next- 这意味着保留对它的临时引用。当然，如果其他人仍然对它有引用，那就不好了。在 Java/C# 中，您只需忽略它。 )

我试图找出一种暗示它而不泄露它的方法，但这有点棘手......

它确实依赖于这不是列表中的最后一个节点。

Answer 2

不完全考虑删除节点，但您可以将下一个节点的数据复制到当前并删除下一个节点：

// pseudocode:
this.data = next.data;
var temp = this.next;
this.next = next.next;
delete temp;

Answer 3

如果节点是内存中的基本结构，则可以将“next”节点的内容复制到已删除节点的内存位置，并释放“next”节点所在的内存。

Answer 4

是的。您保留一个指向前一个列表的下一个指针的指针作为迭代指针。

walk = &head;
while (!match(*walk)) {
    walk = &walk[0]->next;
    if (!*walk) return ;
}
*walk = walk[0]->next;

Answer 5

假设您有指向要删除的节点的指针。将下一个值复制到当前节点。将当前指针替换为下一个指向的节点。

Answer 6

移动数据，而不是链接。查看另一个线程： 当指向前一个节点的指针不可用时，从单个链表中删除中间节点