题目

• 题号：141
• 难度：简单
• https://leetcode-cn.com/problems/linked-list-cycle/

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？

实现

思路1 Hashset

最容易想到的办法就是使用哈希表存储访问过的节点：
遍历数组，每次新访问一个节点，若不在哈希表中则加入；若已存在说明存在环。

思路2 双指针

此外判断链表是否有环的问题有个很典型的解决方法就是利用快慢指针。
即定义一个快指针和满指针，每个循环快指针总是比满指针多遍历一步，那么

• 若链表有环，最后快指针总能再次追上满指针。
• 若链表没环，最后快指针将到达链表的尾部 ```python

  Definition for singly-linked list.

  class ListNode:

  def init(self, x):

  self.val = x

  self.next = None

class Solution: def hasCycle(self, head: ListNode) -> bool: if not head or not head.next: return False

    slowPtr = head
    fastPtr = head.next
    while slowPtr != fastPtr:
        # 因为每次快指针前进两步，所以要检查两步
        if not fastPtr or not fastPtr.next:
            return False
        # 慢指针前进1步，快指针前进2步
        slowPtr = slowPtr.next
        fastPtr = fastPtr.next.next
    # 若跳出循环则说明slowPtr == fastPtr
    return True

``` 时间复杂度：. 其中N是链表中的节点数。
空间复杂度：.