一. 题目

1. 问题1

2. 问题2

二. 思路

1. 哈希表

• 将遍历过的节点存在哈希表，然后依次往下走，若遇到已在哈希表中的，说明存在环。

• 时间O(n)， 空间O(n)。

2. 标记法

• 将走过的节点的值标记为正无穷，遇到标记值就是存在环。

• 时间O(n)， 空间O(1)。

3. 双指针

①问题1

②问题2

4. 统计节点数量

• 每遍历一个点，cnt+1，若cnt超出给定范围，说明存在环。

三. 代码

2. 标记法

class ListNode
{
    int val;
    ListNode next;

    ListNode(int x)
    {
        val = x;
        next = null;
    }
}

class Solution
{
    static final int INF = Integer.MAX_VALUE;

    public boolean hasCycle(ListNode head)
    {
        ListNode ph = head;
        boolean ans = false;
        while (ph != null)
        {
            if (ph.val == INF)
            {
                ans = true;
                break;
            }
            ph.val = INF;
            ph = ph.next;
        }

        return ans;
    }
}

3. 双指针

①问题1

class ListNode
{
    int val;
    ListNode next;

    ListNode(int x)
    {
        val = x;
        next = null;
    }
}

class Solution
{
    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;
    }
}

②问题2

class Solution
{
    public ListNode detectCycle(ListNode head)
    {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast)
            {
                ListNode ans = head;
                while (ans != slow)
                {
                    ans = ans.next;
                    slow = slow.next;
                }
                return ans;
            }
        }
        return null;
    }
}

4. 统计节点数量

class Solution
{
    public ListNode detectCycle(ListNode head)
    {
        for (ListNode l = head, r = head; l != null; l = l.next, r = l)
            for (int i = 0; i < (int) 1e4; ++i)
            {
                r = r.next;
                if (r == null) break;
                if (l == r) return l;
            }
        return null;
    }
}