首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
admin
2018-07-17
31
问题
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
毛泽东在《论持久战》中指出,中国抗日战争取得最后胜利最为关键的阶段是()。
下列南北朝时期我国经济发展的突出特点中,对我国经济格局影响最大的一项是()。
下列对“王与马共天下”的正确理解是()。
魏晋南北朝的手工业技术有所进步,下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料
阅读材料,回答以下问题:今日中国独立自由的地位,已随不平等条约的撤废而获得。然而我们中国国民正确的反应,是义务感的激发与责任心的加强。国家的责任与国民的任务,从此更加重大。建国工作的完成,建国理想的实现,皆有待于我们的奋斗和牺牲。“天下无易事,天下无难事
中华人民共和国恢复在联合国合法席位的时间是()。
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代,外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
“瓜步之战”发生在下列哪两个政权之间?()
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
随机试题
写出贝塞尔公式,举例说明用贝塞尔公式法计算实验标准偏差的全过程。
人造血即血氧液,能够用来代替人类血液,满足临床需求,缓解血液短缺状况。而且人造血标准化的生产流程能够确保其________,输入人造血不用再担心会感染艾滋病、肝炎等疾病,可最大程度降低输血相关传染病的风险。因此,研制和批量生产人造血成为当前的热点。填入画横
患者女性,25岁。因即将出国与同学聚餐后2小时出现上腹部剧痛,伴恶心、呕吐3次,急诊入院。体检:体温37.9℃,血压110/75mmHg,血白细胞计数16.5×109/L。目前该患者首优的护理问题是
患者,女,25岁,因“白带增多7天”就诊。妇产检查:外阴阴道正常,宫颈糜烂,糜烂面积占宫颈面积的1/2,护士评估该患者宫颈糜烂的程度是
信息分类体系必须考虑到不同建设项目参与方所应用的编码体系的情况,建设项目信息分类体系应能满足不同项目参与方高效信息交换的需要。这属于()原则的要求。
以下不属于实施安全检查的行为是()。
想象发展的初级阶段在()。
A、自然连接B、交C、投影D、并A关系R和关系S有公共域,关系T是通过公共域的等值进行连接的结果,符合自然连接,选A。
Kissing,strokingandwildembracesarecommonenough,andnowthequiet,romanticgestureofholdinghandsinpublicisa【M1】__
A、Balancebetweenhumansurvivalandecology.B、Conflictbetweenlesslandandmoreproduction.C、Differencebetweenpresentand
最新回复
(
0
)