black

C++语言程序设计

登录

问答题

简答题

写一算法检测单向链表中是否存在环(whether there is a loop in a link list), 要求算法复杂度(Algorithm’s complexity是O(n)) 并只使用常数空间(space is O(c)). 注意,你只知道一个指向单向链表头的指针。链表的长度是不定的,而且环出现的地方也是不定的,环有可能在头,有可能在中间。而且要求是检测, 不能破坏环的结构.

【参考答案】

设两个指针,开始时全部指向链表头,然后开始循环,每次循环中一个指针下移一项,另一个指针下移两项,一直循环至以下两个条件之......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)

相关考题

问答题 找出两个字符串中最大子字符串,如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"

问答题 中缀表达式A-(B+C/D)*E的后缀形式是什么?

问答题 x=x+1,x+=1,x++,为这三个语句的效率排序。并说明为什么。

All Rights Reserved 版权所有©易学考试网(yxkao.com)

备案号:湘ICP备2022003000号-3