用单链表保存m个整数，结点的结构为：[data][link]，且｜data｜≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如

admin2015-12-30 26

问题用单链表保存m个整数，结点的结构为：[data][link]，且｜data｜≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如下：

则删除结点后的head为：

要求：
给出算法的基本设计思想。

选项

答案算法的基本设计思想算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。因为｜data｜≤n，故辅助数组q的大小为n+1，各元素的初值均为0。依次扫描链表中的各结点，同时检查q[｜data｜]的值，如果为0，则保留该结点，并令q[｜data｜]=1；否则，将该结点从链表中删除。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

到1869年为止，人类已发现了多少种化学元素()。

下列不属于凯末尔主义内容的是()。

建立帝国财政收支总账和元首金库，直接控制和调节全国财政收支的是()。

国民党的第一次代表大会上通过的《中国国民党第一次全国代表大会宣言》，其内容不包括()

二战期间，下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役

下列不是战国时代魏国李悝变法的内容的是()

1628年出版了《心血运动论》一书，论证了血液在全身的循环运动，使生理学发展为科学的是()。

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

清朝，各地督抚将重大问题径寄军机处交皇帝审批，称为()。

诸侯国的国君如何用人呢?有人主张：“左右皆曰不可，勿听；诸大夫皆曰不可，勿听；国人皆曰不可，然后察之，见不可焉，然后去之。”这种主张最终可能出自下列哪位思想家之口()。

设置于路堤填土与软弱土地基之间的透水性材料，可起排水的作用，从而保证地基中孔隙水的顺利排出，这种软基处理方法称()。

在厂房内，用于局部照明的手提灯的电源电压应不超过________。

为证券集中交易提供交易场所及设施的是()

肾精久耗者最常见瘀血证最常见

双胍类降血糖药物的降糖作用机制是

根据《工程建设项目施工招标投标办法》，不属于施工招标文件内容的是()。

在我国银行业风险预警体系实践中，蓝色预警法是一种()。

根据简报所反映的内容范围和所起的作用，简报可以分为()。

在下图所示的图像中，以向上运动为正方向，则表示自由落体运动的物体落地后又以落地速度弹起的图像是()。