已知一个带有表头结点的单链表，结点结构为(data，next)，假设该链表只给出了头指针L，请设计一个时间和空间上尽可能高效的算法，将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。说明你所设计算法的时间复杂度与空间复杂度。

admin2014-04-17 76

问题已知一个带有表头结点的单链表，结点结构为(data，next)，假设该链表只给出了头指针L，请设计一个时间和空间上尽可能高效的算法，将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
说明你所设计算法的时间复杂度与空间复杂度。

选项

答案空间复杂度分析：该算法除去链表本身外，只有O(1)的空间消耗。时间复杂度分析：链表中不同的数值个数有O(n)个。该算法对每个不同的数值，都会对链表中的其他元素扫描一遍，并去掉重复的元素，这个过程的复杂度为O(n)，所以整个算法的时间复杂度为O(n²)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/kexi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简述近代香港问题的形成。

布雷顿森林体系是如何建立的，包括哪些内容?

反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。

“改土归流”政策的根本目的是()。

1938年，英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题，这次会议被称为()，它把英法的绥靖政策推到了顶峰，加速了二战的爆发。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

国民政府对日宣战的时间是()。

“文化大革命”发动的两个纲领性文件是()。

第一国际成立的时间是()。

被尊称为近代蒸汽机的直接祖先的是()。

图中标志的含义是______。

冠心病患者突感心悸、胸闷，血压为90／60mmHg，心尖部第一心音强弱不等；心电图示心房率慢于心室率，二者无固定关系，QRS波增宽为0．12秒，可见心室夺获和室性融合波。诊断为

下列情形中，属于投标人相互串通投标的有()。

单利和复利的区别在于()。

德国心理学家邓克尔发现，人看到某一物品有一种常用的功能后．就很难看出其他新功能，进而影响了问题的解决。这一现象称为()。

《雷雨》中在爱情上表现了最强烈抗争精神的人物是()。

下列属于发文字号的组成要素是()。

ManyforeignerswhohavenotvisitedBritaincallalltheinhabitantsEnglish,fortheyareusedtothinkingoftheBritishIsle

RAID也称为【　　】，它仅有数据条块功能而没有数据冗余功能。

计算机408

学硕统考专业

简述近代香港问题的形成。

布雷顿森林体系是如何建立的，包括哪些内容?

反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。

“改土归流”政策的根本目的是()。

1938年，英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题，这次会议被称为()，它把英法的绥靖政策推到了顶峰，加速了二战的爆发。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

国民政府对日宣战的时间是()。

“文化大革命”发动的两个纲领性文件是()。

第一国际成立的时间是()。

被尊称为近代蒸汽机的直接祖先的是()。

图中标志的含义是______。

冠心病患者突感心悸、胸闷，血压为90／60mmHg，心尖部第一心音强弱不等；心电图示心房率慢于心室率，二者无固定关系，QRS波增宽为0．12秒，可见心室夺获和室性融合波。诊断为

下列情形中，属于投标人相互串通投标的有()。

单利和复利的区别在于()。

德国心理学家邓克尔发现，人看到某一物品有一种常用的功能后．就很难看出其他新功能，进而影响了问题的解决。这一现象称为()。

《雷雨》中在爱情上表现了最强烈抗争精神的人物是()。

下列属于发文字号的组成要素是()。

ManyforeignerswhohavenotvisitedBritaincallalltheinhabitantsEnglish,fortheyareusedtothinkingoftheBritishIsle

RAID也称为【 】，它仅有数据条块功能而没有数据冗余功能。

RAID也称为【　　】，它仅有数据条块功能而没有数据冗余功能。