问答题
简答题
写一算法检测单向链表中是否存在环(whether there is a loop in a link list), 要求算法复杂度(Algorithm’s complexity是O(n)) 并只使用常数空间(space is O(c)). 注意,你只知道一个指向单向链表头的指针。链表的长度是不定的,而且环出现的地方也是不定的,环有可能在头,有可能在中间。而且要求是检测, 不能破坏环的结构.
【参考答案】
设两个指针,开始时全部指向链表头,然后开始循环,每次循环中一个指针下移一项,另一个指针下移两项,一直循环至以下两个条件之......
(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)
点击查看答案