出一道面试时遇到的算法题
题目：
如何判断一个单链表是否有环。即最后一个节点的next指针没有指向NULL，而是指向了前面的某一个节点。
要求：尽量考虑空间/时间复杂度
[解决办法]
菜鸟路过~~~~~
每个节点里面设置一个标志量，遍历了的就是1，没遍历就是0，如果一直遍历下去遇到了已经遍历的，就有环。
[解决办法]
这题怎么感觉那么熟悉……好像做过……
---------------
1、类似1楼的方法。
2、定义两个指针，fast和slow，fast每次走2步，slow每次走1步， 如果有环，那么最终fast和slow会相遇
（可以想象两个人以不同的速度在一个环形跑道上，快的人最终会再追上慢的人）
3、逆转链表，遍历链表并把每个节点的方向逆转（Header指向NULL，下一个节点指向Header……），如果有环的话，新的链表的New_Header肯定和原来的Header相同，（相当于绕了个圈走回来了）
-------------
我的第一想法和1楼的一样……
[解决办法]
个人愚见：
1.按顺序遍历,遍历的个数大于连表中结点的个数说明有环。
[解决办法]
google "步长法"
[解决办法]
[解决办法]
c 专家编程 有讲
--- 追赶法
（一个指针每次移动一步，另一指针每次移动两步）
[解决办法]
6楼头像是谁？告诉我吧。。。
[解决办法]
[解决办法]
[解决办法]
[解决办法]
这是个老题了
[解决办法]
恩。老题了。步长法是可以判断，如果要返回节点，可以用扫描法，只要判断next节点有没有在前面出现过即可。不过从复杂度考虑，只有步长法了。
[解决办法]