若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应

[问答题]

在单链表、双向链表和单向循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间负责性各为多少。

awdsefe

对于单链表：若想要删除结点*p，必须知道*p的前一个结点，使前一个结点指向指针p的下一个结点，再释放p空间。现在不知道前一个结点，故不能删除。

对于双向链表：知道*p指向的结点，将p->next赋值给*p的前一个结点的next，将p->next->front赋值给p->front，如此，便删除了*p

对于循环链表：知道*p指向的结点，再由p的下一个结点指向p的下一个结点的下一个结点，又由于这是一个单向循环链表，所以最终可以遍历到p的前一个结点，将p->next赋值给p前一个结点的next，就删除了*p。

时间复杂度全为O(n)。

发表于 2019-06-23 11:08:49 回复(1)

提交观点

问题信息

链表

上传者：城市里的养猫者

难度：

1条回答 3收藏 3158浏览

扫一扫，把题目装进口袋