首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 说明你所设计算法的时间复杂度和空间复杂度。
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 说明你所设计算法的时间复杂度和空间复杂度。
admin
2014-04-17
40
问题
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
空间复杂度分析:除去链表本身外,只有O(1)的空间消耗。 时间复杂度分析:如果链表无环,那么经过n/2步之后,fast会走到链表的末端,程序结束。如果链表有环,假设经过k步之后slow进入环中(k<n),此时slow和fast之间的距离为m(m<n)。由于fast每次比slow多走一步,那么经过m步之后,fast就会恰好追上slow。两步的时间复杂度均为O(n),所以总的时间复杂度也是O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/5lxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
汉延熹五年(162)皇甫规得罪宦官,论输左校,太学生()等三百人,跟大官僚一起诣阙陈诉,使皇甫规获得赦免。
隋统一全国时,与隋军平定岭南地区有关的人员是()。①洗夫人②慕容三藏③孙夫人④裴矩
西南军阀跟随孙中山拥护护法运动的目的是()。
试述中国共产党诞生的历史条件和意义。
评析郑和下西洋的历史条件和意义。
论述斯巴达的阶级结构、政治制度和社会风尚
商族的远祖可追溯到尧舜时代的契,传说契母简狄吞玄鸟之卵而生契。契便是商人的祖先。以此传说推测,商族是以()为图腾的部落。
二战后世界经济走向统一的过程中,仍然存在着多样性,出现了“两种体系、三种国家”,下列不属于社会主义国家经济类型的是()。
描述滑动窗口机制及其作用。比较停止一等待协议,多帧滑动窗口和后退N帧协议,多帧滑动窗口与选择重传协议的区别。
随机试题
关于刑事责任,下列说法中正确的是()。
某液体物料在一换热器中恒压下从100℃加热到300℃,其恒压平均热容为2.5kJ/(kg.K),加热用介质为高温烟气(可视为理想气体),流量为40kmol/h,恒压下从600℃降到400℃,其恒压平均热容为30.0kJ/(kmol.K),换热器的热损失为3
治疗气滞血瘀型痛经的最佳方剂是
在大跨径连续梁桥施工中,施工简单且不影响通航的方法是()。
某汽车企业生产001型号汽车,年产量10,000台,每台001型号汽车需要A1―001型号轴承1件。该企业年初运用在制品定额法来确定本年度车间的生产任务,相关信息及数据见下表:根据市场和企业状况,装配车间001型号汽车的投入量调整为25,000台,则
2017年3月26日,微信公众号“杂谈黄土地”发布消息称,西部某中学德育处老师指使学生用微型摄像机偷拍,以此来抓获吸烟的同学进行处罚,被抓学生每人每次要交500元罚款。此外,学生带手机进学校也要罚款500元。有网民爆料称,最多的时候一天就有20个学生交了罚
阅读下列说明,回答问题,将解答填入对应栏内。【说明】X省通信运营商拟开发运营支撑系统应用软件,管理企业的业务流程和基础资源。建设单位通过公开招标方式选择了监理单位,以便协助建设单位做好全过程的监理工作。该项目承建单位采用瀑布模型进行软件开发。在项目开发
"Themoregadgetsthereare,the【C1】______thingsseemtoget."saidHonoreErvin,co-authorofTheEtiquetteGirls:ThingsYou
【B1】【B4】
A、Triggerpeople’sanger.B、Influencethecountry’simportandexport.C、Affectthecountry’syoungpeopletostudyabroad.D
最新回复
(
0
)