【数据结构和算法】判断链表中是否有环-视频讲解

B站视频合集：https://www.bilibili.com/video/BV1za411n7Hf

解法一

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

解法二

    public boolean hasCycle(ListNode head) {
        if (head == null)
            return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast)
                return true;
        }
        return false;// 表示没有坏
    }

解法三

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        // 如果当前节点指向自己，表示有环
        if (head.next == head)
            return true;
        ListNode next = head.next;
        // 当前节点指向自己
        head.next = head;
        // 继续检查下一个节点
        return hasCycle(next);
    }

解法四

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null)
            return false;
        ListNode revers = reverseList(head);
        return revers == head;
    }

    // 反转链表（这里不能使用递归的方式）
    private ListNode reverseList(ListNode head) {
        ListNode pre = null;// 相当于反转之后的链表
        while (head != null) {
            ListNode next = head.next;

            head.next = pre;
            pre = head;

            head = next;
        }
        return pre;
    }

反转链表