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

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

admin2014-04-17  49
问题 已知一个带有表头结点的单链表，结点结构为(data，next)，假设该链表只给出了头指针L，请设计一个时间和空间上尽可能高效的算法，将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案空间复杂度分析：该算法除去链表本身外，只有O(1)的空间消耗。 时间复杂度分析：链表中不同的数值个数有O(n)个。该算法对每个不同的数值，都会对链表中的其他元素扫描一遍，并去掉重复的元素，这个过程的复杂度为O(n)，所以整个算法的时间复杂度为O(n2)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kexi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)