首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
admin
2018-07-17
42
问题
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1962~1964年,美国社会学家()经过调查,提出了“人的现代化是国家现代化必不可少的因素”的观点。
下面哪部经典是我国最早的官方史书?()
1962~1964年,美国社会学家()经过调查,提出了“人的现代化是国家现代化必不可少的因素”的观点。
1947年,苏联一些农村的干部和群众,为了调动广大群众生产积极性,在管理制度方面进行改革,其主要措施是()。
外国侵略者火烧圆明园事件是发生在()中。
改革开放以来,乡镇企业的异军突起,其重要意义包括()①改变了公有制经济的主体地位②推动了农村产业结构的现代化进程③加快了农村的现代化进程④开辟了农民致富的新途径
北约和华约两个组织对峙近半个世纪,其影响是()。
材料一1870年代初的南部,虽然也不时出现针对黑人的种族暴行,但在日常生活中,黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权,许多州在维护社会秩序名义下,制定了各种法律,规定黑人与白人必
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
Shoesareoutercoveringsforthefoot.Theyhavesoles,andmosthaveheels.Theupperpartofmostshoesextendnohigherthan
A.逐瘀止血汤B.身痛逐瘀汤C.生化汤D.香棱丸E.少腹逐瘀汤治疗不孕瘀滞胞宫证,应首选()
肝硬化患者出现肾衰竭,最可能的原因是
生产车间管理人员的工资不属于直接人工,应当在发生时计入制造费用。()
()是四川最大的冰川群,也是横断山系和青藏高原东部最大的冰川群。
【2013年江西.单选】古代印度宗教权威至高无上,教育权控制在婆罗门教和()手中。
下列关于公告与通告的区别表述错误的是()。
米格一25效应:前苏联研制的米格一25喷气式战斗机的许多零部件与美国的相比都落后,但因设计者考虑了整体性能,故能在升降、速度、应急反应等方面成为当时世界一流。即所谓最佳整体,乃是个体的最佳组合。下列哪一项属于米格一25效应?
下列属于全国人大常委会职权的是()
A、Themanhadbetterdropmorethanone.B、Theman’scourseisthebestofthefour.C、Themanmustbeanexcellentstudent.D、T
最新回复
(
0
)