220425环形链表——判断一个链表中是否有环

static class Node{
        int val;
        Node next;
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
    public static void main(String[] args) {
            Node node5 = new Node(5, null);
            Node node4 = new Node(4, node5);
            Node node3 = new Node(3, node4);
            Node node2 = new Node(2, node3);
            Node node1 = new Node(1, node2);
            node5.next = node3;
        System.out.println(hasCycle(node1));
    }
    /**
     * 使用集合存储已经遍历过的元素，如果再次遍历到则返回
     * 时间复杂度O(n)，空间复杂度也是O(n)
     * @param node1
     * @return
     */
    private static boolean hasCycle(Node node1) {
        // 定义一个set存储已经遍历过的节点
        Set<Node> nodeSet = new HashSet<>();
        // 循环链表
        while (null != node1) {
            // 如果set中已存在node节点，再次add则返回false
            if (!nodeSet.add(node1)) {
                return true;
            }
            node1 = node1.next;
        }
        return false;
    }

static class Node{
        int val;
        Node next;
        public Node(int val, Node next) {
            this.val = val;
            this.next = next;
        }
    }
    public static void main(String[] args) {
            Node node5 = new Node(5, null);
            Node node4 = new Node(4, node5);
            Node node3 = new Node(3, node4);
            Node node2 = new Node(2, node3);
            Node node1 = new Node(1, node2);
//            node5.next = node3;
        System.out.println(hasCycle2(node1));
    }
    /**
     * 使用双指针，快指针一次前进2个节点，慢指针一次前进一个节点，如果存在环，则这两个指针就一定会相遇
     * 时间复杂度是O(n)，空间复杂度是1
     * @param node1
     * @return
     */
    private static boolean hasCycle2(Node node1) {
        if (null == node1) {
            return false;
        }
        // 定义两个指针，一个慢指针slow，一个快指针quick
        Node slow = node1, quick = node1.next;
        while (slow != quick) {
            // 如果快指针为null或者快指针的下一个节点为null，说明到链表的结尾，那么也不存在环，返回false
            if (null == quick || null == quick.next) {
                return false;
            }
            slow = slow.next;
            quick = quick.next.next;
        }
        // 如果慢指针和快指针相等，则存在环，返回true
        return true;
    }