有一个单链表,提供了头指针和一个结点指针,设计一个函数,在 O(1)时间内删除该结点指针指向的结点。
众所周知,链表无法随机存储,只能从头到尾去遍历整个链表,遇到目标节点之后删除之,这是最常规的思路和做法。
如图所示,删除结点 i,那么只需找到 i 的前驱 h,然后连 h 到 j,再销毁i 即可。虽然可以安全的删除 i 结点,但是是顺序查找找到 i,之后删除,时间复杂度是 O(n)级别的。具体做法就是:顺序查找整个单链表,找到要删除结点 i 的直接前驱 h,把 h额 next 指向i 的 next ,再删除 i 结点即可
现在假设的是我们知道这个单链表里一定存在我们需要删除的结点(也就是存在目标结点),因为是单链表,结点没有前驱,那么找到前驱,我们只能从头结点开始扫描整个链表,那么,我们可不可以去找到要删除结点的下一个结点呢?
时间复杂度为 O(1)的删除单链表结点的方法
如果我们直接找到要删除结点的下一个结点,是非常方便的,不用去遍历整个链表,只需把删除结点 i 的下一个结点j 的内容复制到 i 上,然后把 i 的指针指向 j 的next,然后再删除j 结点。等价于删除了 i 结点。整个过程无需遍历整个链表,时间复杂度是 O(1)级别
继续思考这个思路:这个方法,依靠的是结点的后继指针,如果要删除的结点在末尾,也就说,结点没有后继,怎么处理?
本题目没有给出尾指针,那么此种特殊情况,还是需要从头到尾遍历整个链表,得到该结点的前驱,然后删除该结点。
继续思考,如果单链表只有一个结点,那么删除该结点需要做什么处理?
如果单链表只有一个结点,现在需要删除这个结点,也就是链表的头结点(尾结点),那么在删除之后,需要把头指针指向 NULL处理。
代码实现如下:
typedef struct Node{
int data;
Node *next;
} Node, *List; void deleteNode(List *head, Node *del)
{
Node *p = NULL;
//判断链表是否为空
if (!head) {
cout << "链表为空!" << endl;
exit();
}
//如果删除的结点是尾结点
if (del->next == NULL) {
p = *head;
//仍然需要遍历链表
while (p->next != del) {
//顺次后移
p = p->next;
}
//找到前驱,断链
p->next = NULL;
//删除结点
delete del;
//预防野指针
del = NULL;
}
//如果单链表只有一个结点
else if(*head == del){
//无需断链,直接删除
delete del;
del = NULL;
//头指针处理
*head = NULL;
}
//如果链表里有多个结点,且删除的结点不是尾结点
else{
//无须遍历链表
p = del->next;
del->data = p->data;
del->next = p->next;
delete p;
p = NULL;
}
}
时间复杂度分析:
如果是删除非末位的结点,且结点有n(n>1)个,那么时间复杂度是 o(1),对于尾结点,是 o(n),总得来说,是【(n-1)o(1)+o(n)】/ n,结果还是 o(1),复合要求。
注意
1、考虑问题要全面,不要丢三落四,以为出了结果,就算完成任务了。需要严谨的求学问。
2、这个题目的思路其实是建立在客户事先知道本链表里存在需要删除的结点。如果不知道,我们还是需要先遍历整个链表进行查找!那样时间复杂度还是 o(n)。
3、关于删除结点,往往都是只能想到找到前驱,删除,但是逆向思路看,不一定说,删除结点,就一定要删除这个结点,我们可以找到结点的后继,然后通过内容复制,删除该结点的后继结点,来达到删除该结点一样的效果。
欢迎关注
dashuai的博客是终身学习践行者,大厂程序员,且专注于工作经验、学习笔记的分享和日常吐槽,包括但不限于互联网行业,附带分享一些PDF电子书,资料,帮忙内推,欢迎拍砖!
时间复杂度分别为 O(n)和 O(1)的删除单链表结点的方法的更多相关文章
-
删除单链表节点,时间复杂度为O(1)
一个编程练习,删除单链表一个节点,且时间复杂度控制在O(1)内. 1.核心操作代码如下: struct ListNode { int m_data; ListNode *m_pNext; }; voi ...
-
用O(1)的时间复杂度删除单链表中的某个节点
给定链表的头指针和一个结点指针,在O(1)时间删除该结点.链表结点的定义如下: struct ListNode { int m_nKey; ListNode* m_pNext; }; 函数的声明如下: ...
-
数据结构(C语言第2版)----时间复杂度和单链表
马上要到校招了,复习下相关的基础知识. 时间复杂度是什么? 官方解释: 算法的执行时间需要依据算法所编制的程序在计算机上于运行时所消耗的时间来度量.在算法中可以使用基本的语句的执行次数作为算法的时间复 ...
-
单链表的回文判断(O(n)时间复杂度和O(1)的空间复杂度)
对于单链表来说,判断回文最简单的方法就是遍历链表,将链表中的元素复制到数组中,然后对数组进行判断是否是回文数组,但是这不符合O(1)的空间复杂度. 由于空间复杂度的要求,需要就地操作链表,不能开辟多余 ...
-
在O(n) 时间复杂度,O(1)空间复杂度内反转单链表
在LeetCode中看到判断回文的程序:https://leetcode.com/problems/palindrome-linked-list/ 里面用单链表来存储数据,先反转前半部分的单链表,然后 ...
-
感觉单链表是实现BCL ICollection 的最佳方式,所有操作都能以最小的时间复杂度完成
public interface ICollection<T> : IEnumerable<T>, IEnumerable { int Count { get; }// ...
-
C# - 集合类
C#的集合类命名空间介绍: // 程序集 mscorlib.dll System.dll System.Core.dll // 命名空间 using System.Collections:集合的接口和 ...
-
《数据结构》2.3单链表(single linked list)
//单链表节点的定义 typedef struct node { datatype data; struct node *next; }LNode,*LinkList; //LNode是节点类型,Li ...
-
C#栈
线性表.栈和队列这三种数据结构的数据元素以及数据元素间的逻辑关系完全相同,差别是线性表的操作不受限制,而栈和队列的操作受到限制.栈的操作只能在表的一端进行, 队列的插入操作在表的一端进行而其它操作在表 ...
随机推荐
-
PHP浮点数精度问题
这一段时间维护一个类似团购的系统,需要处理订单,也就难免会处理金额 所以有很多PHP的坑 被我狠狠的踩了~~ 首先我们要知道浮点数的表示(IEEE 754): 简言之 就是 埋下了一个大坑 等着你跳 ...
-
iOS-大神们的博客收集
唐巧的技术博客 http://blog.devtang.comOneV's Den http://onevcat.com破船之家 http://beyondvincent.comNSHipster h ...
-
设为首页 和 收藏本站js代码 兼容IE,chrome,ff
设为首页 和 收藏本站js代码 兼容IE,chrome,ff //设为首页 function SetHome(obj,url){ try{ obj.style.behavior='url(#defau ...
-
java运算优先级
列号 符号 名称 结合性(与操作数) 目数 说明 1 . 点 从左到右 双目 ( ) 圆括号 从左到右 [ ] 方括号 从左到右 2 + 正号 从右到左 单目 - 负号 从右到左 单目 ++ ...
-
winform学习之-----页面设计-20160523
1.将默认的Form属性设置为FormBorderStyle:none 2.picturebox均设置为backgroundImage 3.lable设置自动换行,autosize true,设置Ma ...
-
Redis命令小细节
1. set setnx setex set 将字符串 value的值关联到key ,假设key已经存在,那么覆盖原来的,假设不存在.那么就创建 setnx 将key的值设置为value ...
-
javascript构造函数以及原型对象的理解
以下是一个构造函数的例子 如果是实例方法,不同的实例化,它们引用的地址是不一样的,是唯一的. //定义一个构造函数 function People(name,age){ this.name=name; ...
-
正则表达式入门案例C#
---恢复内容开始--- 在网上百度了好多关于正则表达式的,不过好多都是关于语法的,没有一个具体的案例,有点让人难以入门,毕竟我还是喜欢由具体到抽象的认识.所以我就在这先提供了一个入门小案例(学了了6 ...
-
【Python3之多线程】
一.threading模块 multiprocess模块的完全模仿了threading模块的接口,二者在使用层面,有很大的相似性. 1.开启线程的两种方式(同Process) 方法一 from thr ...
-
为什么Python编程被国家教育如此重视?请开始你的表演!
高考新宠 在高考更改之前,提起编程,人们可能更多的会想起c语言之类的. 然而,高考更始之后,Python这门编程说话一夜之间传进了千家万户. 现实上,在IEEE(美国电气电子工程师学会出书的旗舰杂志) ...