首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
51
问题
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析:该算法除去链表本身外,只有O(1)的空间消耗。 时间复杂度分析:链表中不同的数值个数有O(n)个。该算法对每个不同的数值,都会对链表中的其他元素扫描一遍,并去掉重复的元素,这个过程的复杂度为O(n),所以整个算法的时间复杂度为O(n
2
)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kexi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
体格拉特.帕拉沙尔三世改革的主要内容及其结果。
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
“文化大革命”发动的两个纲领性文件是()。
毛泽东从事了大量理论研究工作,系统阐述了新民主主义的理论,下列选项中,不属于这一范围的是()
罗斯福新政的中心措施是对()的调整。
明代中后期,苏州、松江、嘉兴、()、杭州五府,堪称江南最繁华的城市。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
葡萄牙、西班牙最早走上殖民征服道路,从政治上来说是由于()
随机试题
与腹腔相通的鞘膜积液类型:
在RHEL5系统中,使用mysql命令链接到MySQL数据库服务器以后,执行()操作可用来查看当前服务器的已有数据库列表。
多层降尘室是根据()原理而设计的。
判断一个人在组织中是否是管理者的标准是:他或她是否有()。
下列不属于护士的心理素质的是()。
中药饮片的包装必须注明的内容有
慢性血源性骨髓炎有效的治疗方法是()
根据《生产过程危险和有害因素分类与代码》的规定,生产过程中的危险、有害分为()大类()小类。
如图,直线ι1∥ι2,则α为()。
下面与嵌入式处理器复位相关的叙述中,错误的是()。
最新回复
(
0
)