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

admin2014-04-17 77

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。

中国共产党在抗日民主根据地实行的土地政策是()。

20世纪初出现的法西斯主义实质上也是一种恐怖主义。它与传统的资本主义政治制度的不同主要体现在()。①实行一党专政②抛弃了议会民主制③对外争夺殖民地④强化思想文化的控制

苏俄实施新经济政策的根本目的是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

西南军阀跟随孙中山拥护护法运动的目的是()。

16世纪英国国王推行宗教改革的根本目的是()

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

下列除哪项外，均属于现病史的内容

A．氯喹B．奎宁C．伯氨喹D．乙胺嘧啶E．甲氟喹可用于治疗阿米巴肝脓肿的药是

按我国现行投资构成，下列费用中不属于基本预备费的是()。

每个建设项目都应编制()，这是一个项目的组织设计文件的一部分。

政府投资有(　　)之分。

注意的初级生理机制是()

静态路由广泛应用于哪些网络连接?______。

在下列模式中，能够给出数据库物理存储结构与物理存取方法的是()。

Acoupleoftrucksandthreecranesarescheduledtoarriveattheconstructionsitenolaterthanthe______week.

计算机408

学硕统考专业

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

李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。

中国共产党在抗日民主根据地实行的土地政策是()。

20世纪初出现的法西斯主义实质上也是一种恐怖主义。它与传统的资本主义政治制度的不同主要体现在()。①实行一党专政②抛弃了议会民主制③对外争夺殖民地④强化思想文化的控制

苏俄实施新经济政策的根本目的是()。

下列内容，与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展，在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张，从经济上瓜分世界

西南军阀跟随孙中山拥护护法运动的目的是()。

16世纪英国国王推行宗教改革的根本目的是()

元朝在中央设置中书省、地方则设置行中书省，其目的是()。

下列除哪项外，均属于现病史的内容

A．氯喹B．奎宁C．伯氨喹D．乙胺嘧啶E．甲氟喹可用于治疗阿米巴肝脓肿的药是

按我国现行投资构成，下列费用中不属于基本预备费的是()。

每个建设项目都应编制()，这是一个项目的组织设计文件的一部分。

政府投资有( )之分。

注意的初级生理机制是()

静态路由广泛应用于哪些网络连接?______。

在下列模式中，能够给出数据库物理存储结构与物理存取方法的是()。

Acoupleoftrucksandthreecranesarescheduledtoarriveattheconstructionsitenolaterthanthe______week.

政府投资有(　　)之分。