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

admin2018-07-17 37

问题单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(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://kaotiyun.com/show/f8Ri777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

下面哪部经典是我国最早的官方史书?()

下列事件：①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订，按照时间顺序排列正确的是()。

1920年，苏俄农民中流传着这样的说法：“土地属于我们，面包却属于你们；水属于我们，鱼却属于你们；森林属于我们，木材却属于你们”，它反映的是战时共产主义政策()。

有人说，巴黎和会是一次分赃会议，下列《凡尔赛和约》中哪一方面的内容最能体现这一性质?()。

下列著作被人们称为17世纪物理学、数学的百科全书，并标志着经典力学体系的完成的是()。

试述“轴心时代”(公元前8世纪至前3世纪)中国、印度、希腊三大古典文化系统之异同。

主张“知己知彼，百战不殆”、“势者因利而制权也”的是()。

—棵二叉树的后序遍历序列为DABEC，中序遍历序列为DFBAC，则先序遍历序列为()。

下列哪项不属于淋球菌外膜成分

从1951年起，新华书店不再承担出版、印刷业务。()

依据三层次说，下列选项中不属于组织文化核心层的是()

A．乙醇或甲醛B．丙酮或三氯化碳C．胰蛋白酶D．10％福尔马林固定或微火加热固定微生物抗原的固定

男，46岁。三年前行固定义齿修复，目前咬合疼痛，义齿松动，要求重行固定义齿修复。检查：固定桥修复体己脱位，固位体为，3/4全冠，基牙Ⅰ度-Ⅱ度松动。

钢弦式应变计、钢弦式压力盒在隧道监控量测中应用广泛，此类传感器可在现场直接读取应变(应力)或压力值。()

分配性正义就是在分配领域的公平，指依据一定的标准公平地分配对象物、合理地取得被分配物，即“得其所应得”，它是正义在分配领域的体现。根据以上定义，下列不属于分配性正义获得的是()。