前言:
眼前各位老铁们对“顺序链表中算法时间复杂度为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的 #链表删除结点的时间复杂度