LeetCode 141. 环形链表

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

1. 空间换时间：哈希表法

这个问题有几种解决方案。 如果空间不是问题，最简单的方法是从头开始通过下一个字段探索节点，并将访问的节点存储在哈希表中-仅当我们访问哈希表中已经存在的节点时，存在一个循环。 如果不存在循环，则搜索在结尾处结束（通常通过将下一个字段设置为 null 来表示）。 此解决方案需要 $O(n)$ 空间，其中 n 是列表中的节点数。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        hash_set = set()
        while head:
             if head in hash_set:
                 return True
             hash_set.add(head)
             head = head.next
         return False

2. 暴力解法

不使用额外存储空间且不修改列表的暴力方法是在两个循环中遍历该列表-外循环一遍遍遍历节点，而内循环从头开始并遍历为 到目前为止，由于外循环已经经历了许多节点。 如果外部循环访问的节点被访问两次，则检测到循环。 （如果外部循环遇到列表的末尾，则不存在循环。）此方法的复杂度为 $O(n^2)$ 。

3. 快慢指针

可以使这种想法在线性时间内工作-使用慢指针和快指针遍历列表。 在每次迭代中，将慢指针加1，将快指针加2。 当且仅当两个指针相遇时，列表才具有循环。

原因如下：如果快指针跳过了慢指针，则在下一步中，慢指针将等于快指针。

class Solution:
    def hasCycle(self, head: ListNode) -> bool:

        fast = slow = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

时间复杂度: $O(n)$，n 是链表节点的个数
空间复杂度: $O(1)$, 只使用了两个指针