我是德国的计算机科学专业的学生.我的教授提出使用以下问题来思考:

I'm a student of computer science in Germany. My professor gave use the following question to think about:

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

'Given a reference to a node in a single linked list (which is not the last node). Give an algorithm to delete this element from the list which has O(1) complexity while maintaining the integrity'.

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

I thought about this, but I'm pretty sure, that there is no such algorithm. since it is a single linked list, you must loop through every node in the list until you reach the node which should be delete, because you have to modify the next-Pointer in the node before the deleted. Which would lead to O(n) complexity.

我错过了什么吗?

这取决于节点是否可变(在值上).

It depends on whether or not the nodes are mutable (in value).

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

There is a way of doing it, if you can do what you like with the nodes:

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

All the information from toDelete has now been overwritten, by the information in the old toDelete.next. (Depending on the platform, you may then need to free the old toDelete.next - which means keeping a temporary reference to it. Not good if anyone else still has a reference to it, of course. In Java/C# you'd just ignore it.)

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

I tried to work out a way of hinting at it without giving it away, but it's kinda tricky...

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

It does rely on this not being the last node in the list though.