给定一个链表，返回链表入环的第一个节点。如果不存在环，则返回 null。

为了表示链表中的环，我们使用一个整数 pos 来表示尾部节点指向节点的索引。如果 pos 是 -1，表示链表中不存在环。

提示： 不要修改链表。

例一：
输入： head = [3,2,0,-4], pos = 1
输出： 尾部节点连接的索引为 1 的节点
解释： 链表中存在环，尾部节点连接到了第二个节点。

例二：
输入： head = [1,2], pos = 0
输出： 尾部节点连接的索引为 0 的节点
解释： 链表中存在环，尾部节点连接到了第一个节点。

例三：
输入： head = [1], pos = -1
输出： 不存在环
解释： 链表中不存在环。

/*
 * 142. Linked List Cycle II
 * https://leetcode.com/problems/linked-list-cycle-ii/
 * https://www.whosneo.com/142-linked-list-cycle-ii/
 */

public class DetectCycle {
    public static void main(String[] args) throws InterruptedException {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        DetectCycle solution = new DetectCycle();

        System.out.println(solution.detectCycle(head));

        node.next = head.next.next.next;

        System.out.println(solution.detectCycle(head).val);
    }

    private ListNode detectCycle(ListNode head) {
        //快慢法查找
        ListNode slow = head;
        ListNode fast = head;

        do {
            if (fast == null || fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        //此时从头部开始走，走到同一位置时刚好是进入循环
        while (head != slow) {
            slow = slow.next;
            head = head.next;
        }

        return head;
    }
}