下面输入一个很诡异的链表，暂时称它为“变异链表”，如图4—3所示。从图中可以看出此链表的尾部形成了一个环，请实现一个时间和空间上尽可能高效率的算法来判断输入的链表是否为“变异链表”，要求：说明你所设计算法的时间复杂度和空间复杂度。

admin2014-04-17 65

问题下面输入一个很诡异的链表，暂时称它为“变异链表”，如图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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

新石器时代的房屋建筑根据环境的不同形成了不同的类型，()地区多为干栏式建筑。

马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》

连续五期用全部或大部分的篇幅报道和评论了五四运动这一伟大运动的杂志是()。

汉延熹五年(162)皇甫规得罪宦官，论输左校，太学生()等三百人，跟大官僚一起诣阙陈诉，使皇甫规获得赦免。

我国第一部系统的史学理论著作是()。

列宁在()中系统地阐明了马克思主义的国家学说。

二战后，美国以经济手段扶植和控制西欧的表现是()。

西南军阀跟随孙中山拥护护法运动的目的是()。

简述弭兵之会的背景、过程和结果。

已知散列函数为H(key)=key％11，处理冲突的方法为二次探测法，探测的序列为：1，-1，4，-4，…，j2，-j2(j＜=m／2)。当di＞0时，Hi=(H(key)+di)％m当di＜0时，Hi=(H(key)+di+m)％m散列

在计算机中表示一个圆时，用圆心和半径来表示，这种表示方法称为＿＿＿＿＿＿。

在Oyz正交坐标系中，设图形对y、z的惯性矩分别为Iy和Iz，则图形对坐标原点的极惯性矩为()。

在()方式下可看到Word文档中绘制的图形。

课外辅导是适应学生个别差异、因材施教的重要途径和措施。()

求幂级数的和函数．

在考生文件夹下的“samp1．acedb”数据库文件中已建立了表对象“tEmployee”。请按以下操作要求，完成表的设计。(1)判断并设置“tEmployee”表的主键。(2)设置“性别”字段的默认值为“男”。(3)删除表中

下面是一个栈类的模板，其中push函数将元素i压入栈顶，pop函数弹出栈顶元素。栈初始为空，top值为0，栈顶元素在stack[top-1)中，在下面横线处填上适当语句，完成栈类模板的定义。template＜classT＞classTs

下列关于模板形参的叙述中，错误的是

AndrenaGravidaisthenameofawildbeedecliningintheUnitedKingdomandtheNetherlands.A(31)ofmonthsagotherecentd

A=ColtB=LancerC=GrandisD=OutlanderWhichcar(s)….isforthosewhowantbothlooksandperformance?