单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释

admin2018-07-17 30

问题单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。

选项

答案(1)算法的基本设计思想：设置两个指针(slow，fast)，初始时都指向头结点，slow每次前进1步，fast每次前进2步。如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。当然，当fast先进入到尾部为NULL，则说明链表中不存在环。 (2)算法的实现如下： bool IsExitsLoop(list *head) { list*slow=head， *fast=head；／／定义两个指针 while(fast＆＆fast—>next) ／／都不空 { slow=slow—>next； fast=fast—>next—>next， if(slow==fast) ／／相遇，存在环 break； } return !(fast==NULL｜｜fast—>next==NULL)； } 当fast若与slow相遇时，slow肯定没有走遍历完链表，故算法的时间复杂度为O(N)，空间复杂度为O(1)。

解析

转载请注明原文地址:https://jikaoti.com/ti/hAfjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

汉武帝时派唐蒙领千人，携带食物丝织品等到夜郎进行活动。稍后，汉在巴蜀之南置()。

氏族公社形成的条件和基本标志是()。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

唐代农业取得了很大的进步，其中这一时期先进的耕地工具是()。

20世纪70年代，资本主义经济发展进入“滞胀”时期，对“滞胀”含义的正确表述是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

在社会服务机构中，由于多数员工是受过专业训练的社会工作者或其他专业人士，加上机构的宗旨是为了服务对象谋取幸福和促进社会进步，所以领导应该具有的特征有()。

在工程网络计划的实施过程中，如果需要确定某项工作进度偏差对紧后工作最早开始时间的影响程度，应根据(　　)的差值进行确定。

给水系统无水箱(罐)时，水泵的扬程应满足()。

甲、乙共同出资购买丙所有的位于天府路35号一套价值300万元的房屋，甲、乙与丙之间的债务性质属于()。

法律援助机构办理法律援助案件的方式包括()。

设有教师表(教师号，姓名，年龄，性别，所在系号)，系表(系号，系名)。用户将非常频繁地在这两张表上执行如下查询：SELEC3、教师号，姓名，系名FROM教师表TJOIN系表DONT．所在系号＝D．系号；为了提高查询效率，

以下4个选项中，不能看成一条语句的是

Theprimarypurposeofajusticeisthe____________(防止犯罪和保护无辜).

计算机408

学硕统考专业

汉武帝时派唐蒙领千人，携带食物丝织品等到夜郎进行活动。稍后，汉在巴蜀之南置()。

氏族公社形成的条件和基本标志是()。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

17世纪英国资产阶级革命中，曾利用了古老文件同专制王权作斗争。这一古老文件是()

“二战”爆发的原因是多种因素综合作用的结果，其中最根本的因素是()。

唐代农业取得了很大的进步，其中这一时期先进的耕地工具是()。

20世纪70年代，资本主义经济发展进入“滞胀”时期，对“滞胀”含义的正确表述是()。

西周的官僚制度已经相当完备，官僚机构庞杂，职官名目繁多。周王室的官僚机构分为两大系统，分别是()。

给定页面请求序列RS=cadbebabcd，页框为4，起始为空，写出LRU页面置换过程。

下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

在社会服务机构中，由于多数员工是受过专业训练的社会工作者或其他专业人士，加上机构的宗旨是为了服务对象谋取幸福和促进社会进步，所以领导应该具有的特征有()。

在工程网络计划的实施过程中，如果需要确定某项工作进度偏差对紧后工作最早开始时间的影响程度，应根据( )的差值进行确定。

给水系统无水箱(罐)时，水泵的扬程应满足()。

甲、乙共同出资购买丙所有的位于天府路35号一套价值300万元的房屋，甲、乙与丙之间的债务性质属于()。

法律援助机构办理法律援助案件的方式包括()。

设有教师表(教师号，姓名，年龄，性别，所在系号)，系表(系号，系名)。用户将非常频繁地在这两张表上执行如下查询：SELEC3、教师号，姓名，系名FROM教师表TJOIN系表DONT．所在系号＝D．系号；为了提高查询效率，

以下4个选项中，不能看成一条语句的是

Theprimarypurposeofajusticeisthe____________(防止犯罪和保护无辜).

在工程网络计划的实施过程中，如果需要确定某项工作进度偏差对紧后工作最早开始时间的影响程度，应根据(　　)的差值进行确定。