面试时候问如果给你一个单链表，如何确定里面有没有环？
我答记录开始指针指向的内存地址，之后依次比较，有相同的就返回有环，走到低就返回无环。考官说开始记录的比如说１这个点确实没环，但是后面的２３４点可能构成了一个环。
我答用用数组记录每个指向指向的内存地址，每一个都跟前面的比较，相同返回有环，不相同把地址放入数组中，考官问时间复杂度，我说ｎ平方，问我能不能提高时间效率
我答扩展链表的数据结构，里面加个表示访问没访问过的标示，开始标示全０，之后一个个沿着链表改为１，如果遇到一个点是１，就返回有环。时间复杂度ｎ。考官说很多情况，数据结构是不能改的，如果不改数据结构怎么办。
我没想出来，谁有好办法提高时间效率呢。。
ｐｓ：我再写贴的时候突然想到个方法，每次先把内存地址按数值大小排序，用时间复杂度是ｎｌｏｇｎ的算法排，然后第ｉ个数比较时候，时间复杂度是ｌｏｇｉ的，由于ｉ《＝ｎ，那比较Ｎ个数时间复杂度小于ｎｌｏｇｎ，排加查的时间复杂度就是ｎｌｏｇｎ。排序时间是ｎｌｏｇｎ的有归并，这里用不上，堆，红黑树，大家觉得可行吗？有没有更好的办法？
我答记录开始指针指向的内存地址，之后依次比较，有相同的就返回有环，走到低就返回无环。考官说开始记录的比如说１这个点确实没环，但是后面的２３４点可能构成了一个环。
我答用用数组记录每个指向指向的内存地址，每一个都跟前面的比较，相同返回有环，不相同把地址放入数组中，考官问时间复杂度，我说ｎ平方，问我能不能提高时间效率
我答扩展链表的数据结构，里面加个表示访问没访问过的标示，开始标示全０，之后一个个沿着链表改为１，如果遇到一个点是１，就返回有环。时间复杂度ｎ。考官说很多情况，数据结构是不能改的，如果不改数据结构怎么办。
我没想出来，谁有好办法提高时间效率呢。。
ｐｓ：我再写贴的时候突然想到个方法，每次先把内存地址按数值大小排序，用时间复杂度是ｎｌｏｇｎ的算法排，然后第ｉ个数比较时候，时间复杂度是ｌｏｇｉ的，由于ｉ《＝ｎ，那比较Ｎ个数时间复杂度小于ｎｌｏｇｎ，排加查的时间复杂度就是ｎｌｏｇｎ。排序时间是ｎｌｏｇｎ的有归并，这里用不上，堆，红黑树，大家觉得可行吗？有没有更好的办法？
楼主【crowgns】截止到2008-06-27 11:32:02的历史汇总数据(不包括此帖)：
发帖数:20 发帖分:876
结贴数:17 结贴分:816
未结数:3 未结分:60
结贴率:85.00 % 结分率:93.15 %
楼主加油