仅指定指向该节点的指针时,从单个链表中删除任何节点

Question

这是一个在采访中向我提出的问题.

"内存中有一个链表.你必须删除一个节点.你需要编写一个删除该节点的函数,该节点只删除节点的地址作为输入而不包括任何其他节点(包括头部)"

我给出了类似于下面帖子中回答的答案 - 将下一个节点的内容复制到要删除的节点中并删除下一个节点.

当指向前一个节点的指针不可用时,从单个链表中删除中间节点

但是面试官再次问我,如果我传递最后一个节点的地址怎么办.我告诉他,因为下一个将是一个NULL,将NULL复制到数据字段以及下一个节点的地址也是NULL.然后他告诉我将会出现悬挂指针的问题......我对此并不了解.请问有人可以解决这个问题吗？这是一个通用的解决方案吗？

更新(两天后):再补充一点.考虑到列表末尾没有特殊节点.最后一个节点指向NULL,如果该节点作为输入,则如何使前一个节点指向NULL.还是不可能？

简单地说:如果给一个节点作为函数的输入,那么如何使引用它的指针指向NULL

Answer 1

脚步:

1. 将数据从节点(i + 1)复制到节点(i)
2. 将第二个节点(i + 1)的NEXT复制到临时变量中.
3. 现在删除第二个节点(i + 1)//它不需要指向前一个节点的指针.

功能:

void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}

Answer 2

悬挂指针:

(http://en.wikipedia.org/wiki/Dangling_reference)

计算机编程中的悬空指针和野指针是指向不指向适当类型的有效对象的指针.这些都是违反记忆安全的特殊情况.

删除或取消分配对象时会出现悬空指针,而不修改指针的值,因此指针仍然指向解除分配的内存的内存位置.由于系统可以将先前释放的存储器重新分配给另一个进程,如果原始程序然后取消引用(现在)悬空指针,则可能导致不可预测的行为,因为存储器现在可能包含完全不同的数据.

在您的回答中,要删除给定节点,您实际上删除了下一个节点,该节点可能被指针引用.这就是悬垂指针问题出现的原因.

(1)正如您在备注中说明的那样,没有外部参考列表.(2)面试官说,可能会出现悬垂指针问题.

(1)和(2)都不能同时正确.这意味着某处存在误解.

关于删除最后一个节点:

但是面试官再次问我,如果我传递最后一个节点的地址怎么办.我告诉他,因为下一个将是一个NULL,将NULL复制到数据字段以及下一个节点的地址也是NULL.

我认为你混淆了这两件事:(1)指向NULL的指针p,(2)在其数据字段中具有NULL的链表节点.

假设数据结构是a -> b -> c -> d.将NULL写入d's数据字段不会使c在其next字段中具有NULL指针.

您可以删除最后一个节点,如果链表始终有一个特殊的最后一个节点,将永远不会被删除.例如,a -> b -> c -> d -> LASTLAST在其数据字段中有一个特殊值,表示它实际上是最后一个元素.现在要删除d,你可以删除LAST并在d's数据字段中写入特殊值.

也许这些正是你在面试中试图说的,在这种情况下,你和面试官之间肯定会有一些误解.