问题描述
我是计算机科学在德国的学生。我的教授给使用以下问题来思考：
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'.
我想到了这一点，但我pretty的肯定，有没有这样的算法。因为它是一个单链表，您必须通过列表中的每个节点的循环，直到你达到应删除节点，因为你要修改下，指针在该节点的删除。这将导致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.value = toDelete.next.value
toDelete.next = toDelete.next.next
所有的 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.
这篇关于算法用于在单链表为O（1）复杂性缺失一个元件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！