题目描述：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
这里考察的也是快慢指针。
当然，如果我们用 HashSet ，也可以实现。当时明显不是这道题的考察目的。
我们假设，使用 2 个指针，快指针是慢指针的 2 倍速。如果有环的话，他们一定会相遇，就像 2 个速度不同的运动员在圆型跑道上跑步一样，跑的快的运动员，一定会在第二圈遇上跑的慢的运动员。
在这道题中，慢指针一次走一步，快指针一次走两步，总有一次，快指针会和慢指针相遇。
为了防止面试官问：为什么一定会相遇呢？我查了一下：
这里引用一个知乎大神的答案：
这个问题你可以用数学归纳法来思考。
首先，由于链表是个环，所以相遇的过程可以看作是快指针从后边追赶慢指针的过程。
那么做如下思考：
1：快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。
2：快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。
3：快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。因此，此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。
作者：冯昱尧
也就是说，当两者相差一步时，慢指针走一步，快指针立马就能追上，当两者相差两步时，快指针追不上，但是会离得更近点，也就是相差一步，此时，转化为第一种情况。
好，知道了结题思路，我们代码就好写了：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next ==null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while(slow != null && fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}
当然，还有一些其他的解法，比如修改内容法—— 每遍历一次，设置一个几乎不存在的值，如果下次还遇到这个值，就是有环，不得不说，这个解法很皮。
另一种就是反转法，如果链表是有环的，反转之后，链表头则还是 head。如下图：
代码如下：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null || head.next == null) {
return false;
}
ListNode pre = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
if (next == null) {
if (current == head){
return true;
}
}
current.next = pre;
pre = current;
current = next;
}
return false;
}
}
但是这种方式会修改数据源。
推荐比较标准的方式——快慢指针。
