给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

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

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

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

解法 1

遍历链表，并将访问过的节点放入哈希表，如果没有重复放入，那么该链表就不是环形链表。

def has_cycle(head):
    nodes = set()
    while head:
        if head in nodes:
            return True
        nodes.add(head)
        head = head.next
    return False

执行用时 :44 ms
内存消耗 :18.8 MB

时间复杂度：O(n)，对于含有 n 个元素的链表，我们访问每个元素最多一次。添加一个结点到哈希表中需要花费 O(1) 的时间。

空间复杂度：O(n)，空间取决于添加到哈希表中的元素数目，最多会添加 n 个元素。

解法 2：

通过使用具有不同速度的快、慢两个指针遍历链表，慢指针每次移动一步，而快指针每次移动两步。如果列表存在环，那么两个指针就会在环形部分的某一节点相遇。

def has_cycle(head):
    if not head:
        return False
    slow, fast = head, head.next
    while slow and fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    return False

执行用时 :40 ms
内存消耗 :18.3 MB

时间复杂度：O(n)，n 为链表中结点数，分别考虑下面两种情况。

• 链表中不存在环：
  快指针将会首先到达尾部，其时间取决于列表的长度，也就是 O(n)。

• 链表中存在环：
  我们将慢指针的移动过程划分为两个阶段：非环部分与环形部分
  当慢指针在走完非环部分即将进入环形部分时，快指针已经进入环，当前迭代次数等于慢指针迭代次数，即非环部分长度，记为 N。
  接下来，两个指针将都处于环形部分：慢指针每次移动一步，而快指针每次移动两步，其速度的差值为 1，因此需要经过 指针距离/速度差值 次循环，快指针和慢指针即可相遇。这个距离几乎就是环形部分长度，记为 K，且速度差值为 1，因此环形部分迭代次数约等于 K。
  所以，在最糟糕的情形下，时间复杂度为 O(N+K)，也就是 O(n)。

空间复杂度：我们只使用了慢指针和快指针两个结点，所以空间复杂度为 O(1)。

参考

https://leetcode-cn.com/problems/linked-list-cycle/