用于删除具有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;