Cycle linkedList

public static boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet<>();
    while (head != null) {
        if (!set.add(head)) {
            return true; // 如果添加失败，说明已经存在该节点，即存在环
        }
        head = head.next;
    }
    return false; // 遍历完整个链表，没有发现重复节点，说明不存在环
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Use two pointers, one slow and one fast. If the two pointer finally points the same position, it means there is a cycle. If there is no cycle, the quick pointer will point to null.

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

• Time Complexity: O(n)
• Space Complexity: O(1)