一个链表,怎么实现时间复杂度O(1)删除节点?

solookin 发布于 2014/03/03 00:12
阅读 2K+
收藏 0

【开源中国 APP 全新上线】“动弹” 回归、集成大模型对话、畅读技术报告”

上次面试,面试官问到这个问题,我怎么也想不出来啊.....

链表怎么实现时间复杂度O(1) 删除节点呢?

加载中
0
蛋蛋娃
蛋蛋娃


delete(node *n, node *prior) {

 prior->next = n->next;

free(n);

}

对于单向链表让他把删除节点的前一个节点传进来.开放性题目开放性回答,他要扯淡你跟着扯淡

蛋蛋娃
蛋蛋娃
回复 @solookin : 哈哈,其实只用传删除节点的前面一个节点prior就可以了删除节点的根据prior->next获取,但是为了体现是删除指定节点。就让他多传一个指定节点
solookin
solookin
回复 @蛋蛋娃 : 看你回复这么多,就选你了
蛋蛋娃
蛋蛋娃
回复 @solookin : 要不就删除指定节点的下一个节点,node s=n->next; n->next=n->next->next; free(s);.但是就改变题意了
蛋蛋娃
蛋蛋娃
回复 @solookin : 这个问题理论上就不满足,不然就不会有双向链表了出现了...这个问题就类似于脑筋急转弯,没必要死磕到底。
solookin
solookin
回复 @蛋蛋娃 : 应该不是这样,这样有什么意义...
下一页
0
3_14159265359
3_14159265359
双向链表?单向链表网上取巧的方法是如果要删除节点为A,删除它下一节点B,把B的数据拷到A这里来。个人感觉不可取,如果有外部指针指向B的话就崩了
solookin
solookin
是单向链表,节点定义不能修改。
0
solookin
solookin
并不知道A的指针,只知道这个节点的成员变量的值。
solookin
solookin
他提供的条件就是这样的。 怎么实现O(1)删除?
Shazi199
Shazi199
只知道值还想要o(1)查找,难道还要维护一个Map不成。。
0
风不够骚
风不够骚

谁能搞到O(1)我给谁100万 最多是log

删除前总要先查找吧?

0
您的好友
您的好友
不可能吧。。。 除非有指针已经指向了待删除节点
您的好友
您的好友
我发现我说错了 delete (node* p){ node* q=p->next; p->next=q->next; free(q); } p是要删除节点的前一个节点
solookin
solookin
回复 @您的好友 : 你贴在这里吧
您的好友
您的好友
这个很简单啊 数据结构里链表的基础 如果lz需要 我写给你
whitepig
whitepig
应该是待删除结点的前一个结点地址。。。。
0
眼大无神瞌睡脸
眼大无神瞌睡脸

把当前节点的下一个节点删除,然后把删除节点的数据赋给当前节点;

p->data=p->next->data;

p->next=p->next->next;

狸猫换太子,呵呵

OSCHINA
登录后可查看更多优质内容
返回顶部
顶部