首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 说明你所设计算法的时间复杂度和空间复杂度。
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 说明你所设计算法的时间复杂度和空间复杂度。
admin
2014-04-17
46
问题
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图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
学硕统考专业
相关试题推荐
下列口号中不是五四运动期间学生在示威游行时高呼的是()。
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
1925年10月签订《洛迦诺公约》后,法国外长白里安认为:“我国的安全比以往任何时候都更有保障了。”对此说法不正确的一项是()。
唐朝时,中国和非洲也有来往。下列有关这方面的证据中最具说服力的是()
“文化大革命”发动的两个纲领性文件是()。
下列著作不属于被后世称为清代汉学的“不祧祖先”之人的作品的是()
汉武帝时,为太常博士的弟子兴建学校,名为(),学生入学后免除本人的徭役,学成经考试后,
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
论述新石器时代及其文化类型。
阅读史料,回答以下问题:重庆中央党部,暨中央执监委员诸同志均鉴:今年4月,临时全国代表大会宣言,说明此次抗战之原因,曰:“自塘沽协定以来,吾人所以忍辱负重与倭国周旋,无非欲停止军事行动,采用和平方法,先谋北方各省之保全,再进而谋东北四省问题之合
随机试题
最早把美育与德、智、体“三育”并称的是()
糖异生:
符合乳腺癌的描述是
女性,42岁,无痛性肉眼血尿3个月,膀胱镜检查见膀胱左侧壁有一个2.0cm×1.1cm×1.8cm大小乳头状新生物,膀胱部分切除术后发现病变已侵犯膀胱壁深肌层,这属于国际抗癌联合会分期法中哪一期()
甲上市公司(以下简称“甲公司”)20×1年至20×3年发生的有关交易或事项如下:其他有关资料:甲、乙公司均为增值税一般纳税人,适用的增值税税率均为17%,本题不考虑除增值税外其他相关税费;售价均不含增值税;本题中有关公司均按净利润的10%提取法定盈余公积
质量管理体系的管理评审属于()。
中国的公益领域突然间出现许多新想法,无论是在企业公益活动中,还是在公益基金以及公益组织等领域,这样的事并不鲜见。应该说这是好现象,因为在公益领域,许多人都受新想法的刺激和鼓舞。但是,要真正促进公益的发展,我们还是应该从理想转向“如何去做”,从关注想法转向模
战后发达资本主义国家国内垄断资本发展的新现象主要有
Inshoppingmalls,theassistantstrytopushyouintobuying"agifttothankherforherunselfishlove".Whenyoulogontoa
Wheredoesthewomanwanttogo?
最新回复
(
0
)