单向链表结点删除问题

问题描述:用最快的速度删除单向链表中的某个节点。

分析:前几天室友参加面试时被问到这个问题,感觉还是挺有意思的,我把我的想法给读者分享下,欢迎读者补充。

        如果要想删除链表中的一个节点,必须要知道这个节点的地址,这是很显然的,我们可以在常数时间内删除这个节点,直接把这个节点的

下一个节点的数据复制到该节点中,然后将该节点所指地址指向下一个节点的所指地址,然后将下一个节点删除即可。

       但是这种方法存在限制,如果要删除的节点正好是尾节点,就无能为力了,我们必须要知道删除节点的前一个节点才可以,因此对于这个问题,

只知道要删除节点的地址不一定可以删除,如果再加上链表首地址,那就一定可以办到了,这是面试官的陷阱所在。

        最后再来谈谈时间复杂度把,如果要删除的节点不是尾节点,时间复杂度为O(1),如果是尾节点,那么时间复杂度为O(n),平均起来就是O(1),

因此最快平均可以在O(1)常数时间内做到。

关于具体的代码我就不再写了,读者可以自己去写代码验证。

原文地址:https://www.cnblogs.com/guozhenqiang/p/5467526.html