当仅给出指向该节点的指针时，从单个链表中删除任何节点 [英] 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.
在您的回答中，要删除给定节点，您实际上删除了 next 节点，该节点可能被指针引用.这就是悬空指针问题的产生方式.
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)指向 NULL 的指针 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 写入 d 的数据字段不会神奇地使 c 在其 next 字段中有一个 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 的数据字段中写入特殊值.
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屋！
