内存中存有一单向链表，要求不许分配额外内存，

但可以使用寄存器保存有限的几个变量，对内存作只读访问，

设计一个算法，复杂度为O(n)，求出该链表中是否有环。

：mikedeakins 时间：01-3-2 18:07:03 ID:463796  

一个游标每次移动一个元素，另一个每次移动两个。

如果重合就有环。很难么？

：mataijin 时间：01-3-2 19:52:10 ID:463902  

你看行不行：

我取表头的地址放在一个寄存器，然后指针顺着移动，有与表头地址相同的就是环

：Pipi. 时间：01-3-2 23:16:11 ID:464050  

我觉得mikedeakins的对。

一个比较差的方法，用3个寄存器，一个保存碰到的最大地址，一个保存碰到的最小地址，

一个保存走的步数，要是能结束当然没有环了，要是 步数>最大地址-最小地址 说明有环，

否则就一直走下去直到结束为止(能结束说明没环)

：howardqu 时间：01-3-3 4:36:59 ID:464088  

mikedeakins的算法应该可以，应该多判断一步：

a=head;

b=head->next;

while (1) {

 if (a==b) return -1; //有环

 if (b==null) return 0; //正常

 a=a->next;

 b=b->next;

 if (a==b) return -1; //有环

 b=b->next;

}

：Crab 时间：01-3-5 17:56:54 ID:465237  

mikedeakins 的方法是对的，如果有环，第二个指针总会追上第一个，这时两者地址相同。

算法空间是 0(n) 的，但我还没证明出。

pipi 的做法不一定对，因为链表元素不一定是按序存放的，地址可能完全杂乱无章

：Pipi. 时间：01-3-14 21:25:58 ID:470428  

我记住了最大的地址和最小的地址，举个例子，

最大是2000，最小的是1000，那么里面放的东西不会超过2000-1000+1=1001

个，如果里面有环，不停移动下去，步数会超过个数。