龙空技术网

程序员算法面试题之在O(1)时间内删除链表结点

程序小园 829

前言:

眼前各位老铁们对“顺序链表中算法时间复杂度为o1的”大约比较关注,同学们都需要知道一些“顺序链表中算法时间复杂度为o1的”的相关内容。那么小编也在网络上网罗了一些对于“顺序链表中算法时间复杂度为o1的””的相关资讯,希望同学们能喜欢,姐妹们快快来学习一下吧!

本文参考书籍 《剑指offer》 作者何海涛

01 题目

给定一个单向链表的头节点和一个指针节点,定义一个函数在o(1)时间内删除该节点。

链表节点和函数节点的定义如下:

注意给的待删除结点是链表中的一个指针节点

02 解题

因为给的结点是链表中的节点,我们很容易想到把下一个节点的数值复制到当前节点,然后把指针指向下下一个节点,这样就完成了O(1)时间内操作删除节点。

如果面试官出这种简单的题目时,一定不要急于去写,想清楚所有的边界条件,使代码的健壮性达到最好,才能顺利通过面试。

题目给定的节点在链表中的位置存在以下几种情况

1.需要删除的节点位于链表中间

把4复制到3的位置覆盖,改变next指针指向

2.需要删除的节点位于链表头部

删除方式类似,因为此时待删除节点的next都不为空

3.需要删除的节点位于链表尾部

此时待删除节点的next为null,只能循环遍历到最后,将节点4的next置位NULL

4.需要删除节点的next为null,且只有一个节点

节点置为null即可。

所以综上,总的情况分为两种,需要删除的节点

node.next != null

node.next=null 再分为两种,只有一个节点时,有多个节点时。

03 代码

04 时间复杂度

对于 n-1个非尾节点,删除节点需要O(1),对于尾节点来说,需要顺序查找,时间复杂度为O(n),所以综合下来平均时间复杂度[((n-1)*O(1) + O(n))/n]=O(1)

05 需要注意的

以上讨论都是假设,待删除节点存在于链表当中,由于时间复杂度的限制,所以判断节点是否存在于链表中的代码,需要放在调用它的代码中实现

标签: #顺序链表中算法时间复杂度为o1的 #链表删除结点的时间复杂度