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

Question

我是德国计算机科学专业的学生。我的教授用下面的问题来思考:

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

我考虑过这个，但我很确定，没有这样的算法。由于是单链表，必须循环遍历链表中的每一个节点，直到到达要删除的节点，因为必须修改删除前节点的next-Pointer。这将导致 O(n) 复杂度。

我错过了什么吗？

Answer 1

这取决于节点是否可变(值)。

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

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

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

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

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