在 O(1) 时间内删除链表节点

el/2024/7/13 11:52:36
解题思路
① 如果该节点不是尾节点,那么可以直接将下一个节点的值赋给该节点,然后令该节点指向下下个节点,再删除下一个节点,时间复杂度为 O(1)。② 如果链表只有一个节点,那么直接② 否则,就需要先遍历链表,找到节点的前一个节点,然后让前一个节点指向 null,时间复杂度为 O(N)。综上,如果进行 N 次操作,那么大约需要操作节点的次数为 N-1+N=2N-1,其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数,N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2,因此该算法的平均时间复杂度为 O(1)。
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {if (head == null || tobeDelete == null)return null;if (tobeDelete.next != null) {// 要删除的节点不是尾节点ListNode next = tobeDelete.next;tobeDelete.val = next.val;tobeDelete.next = next.next;} else {if (head == tobeDelete)// 只有一个节点head = null;else {ListNode cur = head;while (cur.next != tobeDelete)cur = cur.next;cur.next = null;}}return head;
}

 


http://www.ngui.cc/el/5179136.html

相关文章

题目描述 一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。

题目描述 一个链表中包含环,请找出该链表的环的入口结点。要求不能使用额外的空间。可以参见剑指offer上的原题。代码如下: package cn.cqu.edu;public class NodeOfLoop {class ListNode {int val;ListNode next null;ListNode(int val) {this.val v…

目标检测中mAP的定义

作者:nowgood 链接:https://www.zhihu.com/question/53405779/answer/506000532 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 目标检测中衡量识别精度的指标是mAP(mean averag…

java jdk中的动态代理和Cglib中的动态代理的解析

为什么要用动态代理? 因为静态代理需要额外编写代理类,对于每一个要代理的对象,都要书写一个额外的代理类。 使用代理的原因? 有些类是不能够直接访问的或者有些访问要经过特殊处理。 1. Java JDK中的动态代理 java jdk中的动态…

求1+2+3+4+5+..+n

题目描述 求123...n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。 其主要思想是递归,这个程序很美。 package cn.cqu.edu;public class Sum_Solution1 {public int Sum_Solution(in…

tomcat运行java web时,报这个错:org.springframework.beans.factory.BeanCreationException

具体出错信息如下: 严重: StandardWrapper.Throwable org.springframework.beans.factory.BeanCreationException: Error creating bean with name userController: Injection of autowired dependencies failed; nested exception is org.springframework.beans.factory.Bea…

eclipse下springmvc+spring+maven+mybatis+mysql的搭建,并实现增删改查

eclipse下SpringMVC+Maven+Mybatis+MySQL项目搭建 这篇文章主要讲解在eclipse环境下SpringMVC+Maven+Mybatis+MySQL的项目搭建过程。 创建Maven工程。右击-->New->Other 点击->Manven Porject 点击->勾选快速框架 输入项目名,包(Packaging,如果只是普通的项目,…

大数据笔试面试题

问题: 有一个包含20亿个全是32位整数的大文件,在其中找到出现次数最多的数,但是内存限制只有2G. 解题思路:先将这个20亿个整数进行哈希分流,比如说分别分流到16个小文件中,然后用哈希表分别计算出每一个小…

c/c++中动态内存分配与回收与从void*类型隐式转换为int*类型

最常见的差异之一是,C允许从void*隐式转换到其它的指针类型,但C++不允许。下列是有效的C代码。从void*类型隐式转换为int*类型,但要使其在C和C++两者皆能运作,就需要使用显式转换。 c语言版本的: #include <stdio.h> #include <stdlib.h>#define high 2 #de…

c语言数据类型本质及其分析

c语言的数据类型如下&#xff1a; 数据类型的本质是固定内存大小区域的别名。数据类型的作用是编译器预算对象&#xff08;变量&#xff09;的内存大小&#xff0c;从而为其分配。求数据类型的大小可以用sizeof&#xff08;int&#xff09;。数据类型的别名可以用typedef来自定…