[Leetcode] 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?

链表题，要求判断链表中是否存在一个环。最简单的思想就是用一个hashset来将所有的链表节点存储起来，在遍历链表的时候如果找到一个存在于hashset的节点，说明存在一个环，否则遍历完链表，说明没有环存在。

public boolean hasCycle(ListNode head) {
        HashSet set = new HashSet();
        ListNode temp = head;
        while(temp != null) {
            if(set.contains(temp) == true) {
                return true;
            }
            else {
                set.add(temp);
                temp = temp.next;
            }
        }
        return false;
}

但是上面的解法空间复杂度为O(n)。另一种解法只需要O(1)的空间复杂度，即使用快慢指针的方法，如果链表中有环，那么快指针必然会在环内追上慢指针，否则快指针必然先变为null。

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head, fast = head;
        
        do {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) {
                return true;
            }
        }while(slow != null && fast != null && fast.next != null);
        
        return false;
    }