首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用C或C++语言描述算法,关键之处给出注释
admin
2018-07-17
33
问题
单链表有环,是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
(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
学硕统考专业
相关试题推荐
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
在1959年中共中央召开的庐山会议上遭到错误批判的是()。
巴黎和会召开的时间是()。
第一个五年计划的具体时间段是()。
阅读材料,回答以下问题:材料一:甘地认为,非暴力抵抗是印度争取摆脱殖民桎梏的唯一正确办法;同时,他认为非暴力抵抗并不意味着对外国统治和其他罪恶的屈服。他写道:“我深信假如只有在怯懦和暴力两者之间加以选择时,我将劝人选择暴力……我宁愿要印度用暴力来保护自己
鸦片战争前中国同英国相比在政治、经济和军事上存在着哪些差距?到19世纪60年代,外来因素使中国社会出现了哪些变化?变化中进步的主流是什么?
在1919年巴黎和会上,美国总统威尔逊因博学多才、工于辞令而享有“百灵鸟”之称,但其美好的幻想一旦碰到“老虎”和“狐狸”,顿时变成又聋又哑的堂吉诃德。此处的“老虎”和“狐狸”分别是指()。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
皮肤有外伤的人不得配制和使用剧毒化学试剂。
外伤性肢体离断,下列哪种说法不正确
根据中医望诊理论,阳虚、血虚的病证常见的舌色是()。
重大事故、较大事故、一般事故自收到事故调查报告之日起()日内作出批复。
有两个均能满足生产要求的施工方案可供选择,在两方案均需增加投资时,应选择( )的方案。
会员制期货交易所理事会会议结束之日起15日内,理事会应当将会议决议及其他会议文件报告中国证监会。()
设z=+g(ex,siny),其中f二阶连续可导,g二阶连续可偏导,求
A、Lackofvitaminsisthemaincauseofskincancer.B、Newresearchprovesthatsunbathingcausesnoproblemsatall.C、Thedang
Pregnancymothersaregettinganewtooltohelpkeepthemselvesandtheirbabieshealthy:pregnancytipssentdirectlytothei
Tobeasuccessfulbusinessowner,youmustknowyourmarket.Yourbusinesswon’tsucceedjust【B1】youwantittosucceed.Determ
最新回复
(
0
)