这是一个在采访中向我提出的问题.
"内存中有一个链表.你必须删除一个节点.你需要编写一个删除该节点的函数,该节点只删除节点的地址作为输入而不包括任何其他节点(包括头部)"
我给出了类似于下面帖子中回答的答案 - 将下一个节点的内容复制到要删除的节点中并删除下一个节点.
但是面试官再次问我,如果我传递最后一个节点的地址怎么办.我告诉他,因为下一个将是一个NULL,将NULL复制到数据字段以及下一个节点的地址也是NULL.然后他告诉我将会出现悬挂指针的问题......我对此并不了解.请问有人可以解决这个问题吗？这是一个通用的解决方案吗？
更新(两天后):再补充一点.考虑到列表末尾没有特殊节点.最后一个节点指向NULL,如果该节点作为输入,则如何使前一个节点指向NULL.还是不可能？
简单地说:如果给一个节点作为函数的输入,那么如何使引用它的指针指向NULL
如何删除单链接列表中的节点,只有一个指针指向要删除的节点？
[开始和结束指针未知,可用信息是指向应删除的节点的指针]
我是德国的计算机科学专业的学生.我的教授用了以下问题来思考:
'给定对单个链表中的节点的引用(不是最后一个节点).给出一个算法,从列表中删除该元素,该元素具有O(1)复杂度,同时保持完整性.
我想到了这一点,但我很确定,没有这样的算法.因为它是单个链表,所以必须遍历列表中的每个节点,直到到达应该删除的节点,因为您必须在删除之前修改节点中的下一个指针.这将导致O(n)复杂性.
我错过了什么吗？