给定一个链表，判断其中是否有环。

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

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

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

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

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

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

        HasCycle solution = new HasCycle();

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

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

        System.out.println(solution.hasCycle(head));
    }

    private boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;

        //快慢法查找
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null && slow != fast) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if (fast == null || fast.next == null)
            return false;

        return true;
    }
}