141. 环形链表

题目：https://leetcode-cn.com/problems/linked-list-cycle/

代码：

class Solution {

    public boolean hasCycle(ListNode head) {
        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //进行赛跑
        do {
            //跑到尽头证明不存在环
            if (fast == null || fast.next == null) {
                return false;
            }
            //慢指针走一步
            slow = slow.next;
            //快指针走两步
            fast = fast.next.next;
        } while (fast != slow);
        //快指针套若干圈后追上慢指针，证明有环
        return true;
    }

}

题目有一大堆废话讲解了pos变量的作用，实际上这个变量只是oj系统他自己在用，我们并不需要了解。题目最终要求就是：给定一个链表，判断链表是否存在环，如果可以的话使用O（1）内存解决此问题。

本题有很多取巧的办法来解答，比如：
1、直接改节点的val值为一个特殊值，判断这个特殊值在遍历中是否再次出现。
2、因为题目有给定测试用例最大节点数，所以直接遍历，每遍历一次次数+1，次数大于最大节点数则可以认为存在环。

上述都是投机的办法，实际业务中如果有需求肯定是不能这么干的，那么我们该怎么办呢？我们可以使用快慢指针的办法（龟兔赛跑）。

定义快（兔子），慢（乌龟）两个指针，快指针每次移动2格，慢指针每次移动1格，则快指针一定跑的比慢指针快。
1、假如快指针一直跑最终出现了null值的情况，则证明跑到了终点，则链表不存在环（为什么只需要判断快指针？因为慢指针跑的慢，跑的都是快指针跑过的路，不需要多次一举）
2、假如链表中存在环，则快慢指针一定会在环中一直转圈无止尽的跑下去，这个时候，由于快指针跑2格，慢指针跑1格，从物理学角度来说，以慢指针为参照物，则快指针相对于慢指针只跑1格，最终快指针一定会套圈慢指针与慢指针相遇。

综上所述使用代码实现即可。