删除单链接列表中的节点
如何删除单链接列表中的节点,只有一个指针指向要删除的节点?
[开始和结束指针未知,可用信息是指向应删除的节点的指针]
您可以删除节点而不获取上一个节点,方法是让它模仿以下节点并删除该节点:
void delete(Node *n) { if (!is_sentinel(n->next)) { n->content = n->next->content; Node *next = n->next; n->next = n->next->next; free(next); } else { n->content = NULL; free(n->next); n->next = NULL; } }
如您所见,您需要专门处理最后一个元素。 我正在使用一个特殊节点作为标记节点来标记具有content
的结尾, next
是NULL
。
更新:行Node *next = n->next; n->next = n->next->next
Node *next = n->next; n->next = n->next->next
基本上对节点内容进行混洗,并释放节点:您在以下位置获取对节点B的引用的图像:
A / To be deleted next ---> B next ---> C next ---> *sentinel*
第一步是n->content = n->next->content
:将以下节点的内容复制到要“删除”的节点:
A / To be deleted next ---> C next ---> C next ---> *sentinel*
然后,修改next
要点:
A / To be deleted next ---> C /---------------- next ---| C | next ---> *sentinel*
实际上释放了以下元素,进入最后的案例:
A / To be deleted next ---> C next ---> *sentinel*
不可能。
有些黑客可以模仿删除。
但是,实际上没有一个会删除指针所指向的节点。
如果外部指针指向列表中的节点,则删除以下节点并将其内容复制到要删除的实际节点的流行解决方案会产生副作用,在这种情况下,指向后续节点的外部指针将变为悬空。
你可以在这里找到关于SO的讨论。
这种限制下唯一明智和安全的选择是标记删除的节点而不实际取消链接,将其推迟到以后的时间。