首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
admin
2018-07-17
45
问题
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(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
学硕统考专业
相关试题推荐
标志着南京国民政府在全国范围内形式上完成统一的事件是()。
1934年9月苏联加入国联,对此说法错误的一项是()。
万历年间,()的获得使得佃农与地主之间只存在单纯的经济强制关系,没有人身依附关系
下列标志着周王室在春秋时代的地位一落千丈,仅存虚名的选项是()
为了巩固政治统治、发展经济,南京国民政府采取了一系列的财政、经济改革,下列选项中不正确的是()
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
三国鼎立局面的关键性战争是()。
中古时代实行索贡巡行赋税征收方式的国家是()。
美国财政部长福勒得意地宣称:“各个行星围绕着太阳转,各国货币围绕着美元转。”这句话的实质含义是()。
IP数据报的报文格式如下图所示。在没有选项和填充的情况下,报头长度域的值为()。
随机试题
使用Excel2010中的_____功能,可以预置一种单元格格式,并在指定的某种条件被满足时自动应用于目标单元格。
麻醉前用药中以减少呼吸道分泌物为目的的药物是
胸闷泛恶,彻夜不寐,大便秘结者,当用()不寐而脘腹胀满,嗳腐吞酸者,当用()
使用胰岛素应告知病人警惕出现下列哪种情况
砌体表面的平整度、垂直度、()及砂浆饱满度均应按规定随时检查校正。
可燃气体探测器按使用方式分类,包括()。
已知a、b互为相反数,并且3a-2b=5,则a2+b2=_______.
谋划和系统部署重大科技基础设施建设,对于增强我国原始创新能力,实现从科技大国迈向科技强国的目标具有重要意义。为此我国制定了建设重大科技基础设施的一系列目标。下面关于建设目标的说法.表述有误的是()。
Shelookedonhim______averygreatprofessor.
A、7:00B、10:00C、8:00D、8:30D
最新回复
(
0
)