首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 给出算法的基本设计思想。
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求: 给出算法的基本设计思想。
admin
2014-04-17
115
问题
下面输入一个很诡异的链表,暂时称它为“变异链表”,如图4—3所示。从图中可以看出此链表的尾部形成了一个环,请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:设置两个指针fast和slow,初始值都指向头结点,slow每次前进一步, fast每次前进两步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定 相遇。当然,如果某时刻fast或者fast→next为空指针,则为无环链表。 可能疑问点:如果有环,为什么两个指针fast和slow必然重合?会不会每次都恰好错过? 提示:因为fast每次走两步,而slow每次走一步,所以它们之间的差距是一步一步缩小 的。当slow进入环入E1点后,fast和slow之间的差距将会一步步缩小,如4→3→2→1→0,到0的时候就重合了。其实这是一个追击问题,是一个比较成熟的定理。
解析
转载请注明原文地址:https://kaotiyun.com/show/ulxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第三世界所共有的特征及崛起的标志是什么?
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
为了加强对地方的控制,唐太宗根据山川形势,把全国划分成10个(),经常派官员监察地方官吏。
以城市为重点的整个经济体制改革的中心环节是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
所罗门死后不久,以色列犹太王国遂分裂为北方的以色列王国和南方的犹太王国。后来,两国分别为哪两个国家所灭?()
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
被尊称为近代蒸汽机的直接祖先的是()。
简述苏联和南斯拉夫之间的冲突。
随机试题
A.PSG检查睡眠时,口鼻气流停止时,记录不到膈肌和胸壁肌活动B.PSG检查睡眠时,口鼻气流停止时,膈肌和胸壁肌活动明显C.PSG检查睡眠时,最低血氧低于80%D.PSG检查睡眠时,RD124,血氧89%E.PSG检查睡眠时,RD1>20,血氧>9
A.特异性识别与杀伤感染细胞B.阻止病毒从黏膜入侵机体C.中和病毒与调理作用D.广谱抗病毒作用E.释放大量细胞因子在局部免疫中,分泌型IgA发挥抗病毒作用的方式是
用聚维酮碘消毒表面。喷射后湿润应保持
战略管理理论结构的基本形成时期是在()。
梁老师在开展《走进敦煌》鉴赏教学时,在教室里贴上了许多敦煌壁画的图片,并播放了关于敦煌的专题片。这种教学方法属于()。
下列关于经济指数的说法正确的是:
设α1,α2,…,αn为n个n维列向量,证明:α1,α2,…,αn线性无关的充分必要条件是
WhatisthecauseofanothermessydayinNewEngland?
AGreatFriendshipThomasJeffersonandJamesMadisonmetin1776.Couldithavebeenanyotheryear?Theyworkedtogethers
Cursive(手写体,草书),theartofpenmanshipcastasideinrecentyearsasschoolsincreasinglyfocusonkeyboarding,maybegetting
最新回复
(
0
)