当只给出指向该节点的指针时，从单个链表中删除任何节点 [英] Deleting any node from a single linked list when only pointer to that node is given
问题描述
这是在面试中给我的一个问题。
This is a question posed to me in an interview.
内存中有一个链表，你必须删除一个节点，你需要写一个函数来删除该节点，该节点仅将要删除的节点的地址作为输入，而没有其他（包括头）
"A single linked list is there in the memory. You have to delete a node. You need to write a function to delete that node, which takes only the address of the node to be deleted as input and nothing else(including head)"
我将答案类似于在下面的回答中 - 将下一个节点的内容复制到要删除的节点中，并删除下一个节点。
I gave the answer similar to the one answered in the below post -- Copying the contents of the next node into the node to be deleted and deleting the next one.
但面试官再次问我，如果我传递最后一个节点的地址，该怎么办？我告诉他，因为下一个将是一个NULL，将该NULL复制到数据字段以及下一个也是NULL的节点的地址。然后他告诉我会有一个悬挂指针的问题，我不明白一点。有人可以扔光这个问题吗？有没有一个通用的解决方案？
But the interviewer asked me again, what if I pass the address of the last node. I told him, since the next will be a NULL, copy that NULL into the data field along with the address to the next node which is also NULL. Then he told me there will be a problem of dangling pointers... which I didn't understand a bit. Can some one please throw light into this problem ? Is there a generic solution to this ?
更新（两天后）：有一点额外。考虑到列表末尾没有特殊节点。并且最后一个节点指向NULL，并且如果该节点被给定为输入，则如何使之前的最后一个节点指向NULL。或者是不可能的吗？
Update (Two days later) : A little bit additional. Considering there is no special node at the end of the list. And the last node points to NULL and if that node is given as input, how to make the before last node point to NULL. Or is it impossible ?
简单地说：如果一个节点作为一个函数的输入，如何使引用它的指针指向NULL
Simply put : If a node is given as input to a function, how to make the pointer that references it, point to NULL
推荐答案
悬挂指针：
（http： /en.wikipedia.org/wiki/Dangling_reference）
(http://en.wikipedia.org/wiki/Dangling_reference)
计算机编程中的悬挂指针和野生指针是
指针，不指向有效对象适当的类型。
这些是内存安全违规的特殊情况。
Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations.
当对象被删除或解除分配时，浮动指针出现，
不修改指针的值，使指针仍然
指向释放内存的内存位置。由于系统
可能将以前释放的内存重新分配到另一个进程，如果
原始程序然后取消引用（现在）悬挂指针，
可能会导致不可预测的行为，因为内存可能现在包含
完全不同的数据。
Dangling pointers arise when an object is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location of the deallocated memory. As the system may reallocate the previously freed memory to another process, if the original program then dereferences the (now) dangling pointer, unpredictable behavior may result, as the memory may now contain completely different data.
在您的答案中，要删除给定的节点，您实际删除下一个节点，它可能被指针引用。这就是指针问题的出现。
In your answer, to delete the given node you actually delete the next node, which might be being referenced by a pointer. That's how dangling pointer problem arise.
（1）如您在说明中所阐述的那样，没有对列表的外部引用。
（2）面试官说，悬挂指针问题可能会出现。
(1) There are no outside references to the list, as you clarify in a note. (2) Dangling pointer problem can arise, as the interviewer said.
同时，（1）和（2）都不能正确。
Both (1) and (2) cannot be correct at the same time. Which means there is a misunderstanding somewhere.
关于删除最后一个节点：
About Deleting the Last Node:
但面试官再次问我，如果我通过
最后一个节点的地址怎么办？我告诉他，由于下一个将是一个NULL，将NULL
复制到数据字段中，并将地址复制到
的下一个节点也为NULL。
But the interviewer asked me again, what if I pass the address of the last node. I told him, since the next will be a NULL, copy that NULL into the data field along with the address to the next node which is also NULL.
我认为你很困惑这两件事情：（1）指向p的指针，（2）在其数据字段中具有NULL的链表节点。
I think you are confusing these two things: (1) A pointer p that points to NULL, (2) A linked list node that has NULL in its data field.
假设数据结构是 a - > b - > c - > d 。将NULL写入数据字段不会使c在其下一个字段中有一个NULL指针。
Suppose the data structure is a -> b -> c -> d. Writing NULL to d's data field will not magicly make c to have a NULL pointer in its next field.
如果链接列表始终具有永远不会被删除的特殊上一个节点，您可以删除最后一个节点。例如， a - > b - > c - > d - > LAST 其中LAST在其数据字段中具有特殊值，表示它真的是最后一个元素。现在删除d，可以删除LAST，并在d's数据字段中写入特殊值。
You can delete the last node if the linked list always has a special last node that will never be deleted. For example, a -> b -> c -> d -> LAST where LAST has a special value in its data field that denotes it is really the last element. Now to delete d, you could delete LAST and write the special value in d's data field.
也许这些正是您在面试中尝试告诉的，在这种情况下，您和面试官之间必然会有一些误会。
Maybe these are exactly what you tried to tell during the interview, in which case there must have been some miscommunication between you and the interviewer.
这篇关于当只给出指向该节点的指针时，从单个链表中删除任何节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
