142. 环形链表 II

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

代码：

class Solution {

    public ListNode detectCycle(ListNode head) {
        //定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //进行赛跑
        do {
            //跑到尽头证明不存在环
            if (fast == null || fast.next == null) {
                return null;
            }
            //慢指针走一步
            slow = slow.next;
            //快指针走两步
            fast = fast.next.next;
        } while (fast != slow);

        //快指针套若干圈后追上慢指针，证明有环
        ListNode first = head;
        //first每走一个节点就让fast跑一圈，如果发现first等于fast，则first是环的起点
        while (true) {
            do {
                if (first == fast) {
                    return first;
                }
                fast = fast.next;
            }while (fast != slow);
            first = first.next;
        }
    }

}

在141. 环形链表的基础上进行改造，使用快慢指针找到存在环之后，我们新定义一个first指针，通过判断first指针是否在环中来获取环的起点，如果不在环中则让first = first.next。

那么我们如何判断first是否在环中呢？我们可以让slow指针停止作为标杆，fast指针继续循环转圈，但步长修改为1，通过判断fast是否等于first来确定是否在环中，slow为标杆防止死循环，具体操作见红色部分代码。