Leetcode 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

题意：判断一个链表中是否存在环。follow up要求能否不用额外空间。

思路：
如果可以用额外空间，那么用一个HashSet记录已经遍历过的ListNode，如果当前遍历到的ListNode存在于HashSet，就存在一个环。

不用额外空间的方法，是用一个慢指针、一个快指针，慢指针一次移动一步、快指针一次移动两步，如果存在环，那么快慢指针迟早会相遇。

public boolean hasCycle(ListNode head) {
    if (head == null) {
        return false;
    }

    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return false;
}