方法一：哈希表

我们可以通过检查一个结点此前是否被访问过来判断链表是否为环形链表。常用的方法是使用哈希表

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

            temp1 = temp1.next;
        }

        return false;

    }

时间复杂度和空间复杂度都是o（n）

方法二：双指针

通过使用具有 不同速度 的快、慢两个指针遍历链表，空间复杂度可以被降低至 O(1)。慢指针每次移动一步，而快指针每次移动两步。

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

时间复杂度：o（n）
空间复杂度：o（1）

链表--环形链表（leetcode 141

原文：https://www.cnblogs.com/swifthao/p/13066670.html