题目描述

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

样例

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

进阶：

你能用 $O(1)$（即，常量）内存解决此问题吗？

算法分析

快慢指针

$fast$ 指针从原点每次走2步， $slow$ 指针从原点每次走1步

1、当链表不存在环形时， $fast$ 指针一定会事先走到 $null$，则返回 $false$
2、当链表存在环形时，$A$ 点是起点，$B$ 点是入口，$C$ 点是两个指针的第一次相遇点，假设 $AB = x$ ，当 $slow$ 指针走了 $x$ 距离时， $fast$ 指针一定会在环上的某一个点上，紧接着 $fast$ 每次走两步，$slow$ 每次走一步，速度不一致，他们一定会在环上某一点上相遇

时间复杂度 $O(n)$

假设 $AB = x$ ，总长度是 $n$ ，则环的长度是 $n - x$ ，当 $slow$ 指针走到$B$点时，共走了 $x$ 步， $fast$ 指针，共走了 $2x$ 步，因此前半部分两指针共走了 $3x$ 步，顺时针看 $fast$ 指针到 $slow$ 指针的距离最多是 $n - x$ ，因此最多走 $n - x$ 次， $fast$ 指针就会追上 $slow$ 指针，则 $fast$ 指针走了 $2(n - x)$ 步， $slow$ 指针走了 $n - x$ 步，因此后半部分两指针共走了 $3(n - x)$ 步，因此时间复杂度是 $3x + 3(n - x) = 3n = O(n)$

Java 代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode fast = head.next;
        ListNode slow = head;

        while(fast != null)
        {   
            if(fast == slow) return true;
            fast = fast.next;
            if(fast != null) fast = fast.next;
            slow = slow.next;
        }

        return false;

    }
}