# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle1(self , head: ListNode) -> bool:
        ########
        # 快慢指针 
        # 设置虚拟头结点 
        # 设置快慢指针
        slow=ListNode(0)
        slow.next=head
        fast =head
        while fast and fast.next:
            #print(pre.val,cur.val)
            if slow ==fast:
                return True  
            slow=slow.next
            fast=fast.next.next
        return False 

    def hasCycle(self , head: ListNode) -> bool:
        # 解法2: 哈希表    时间复杂度 o(n) 空间复杂度O(n)  每个节点保存在哈希表
        st=set()
        cur =head 
        while cur :
            if cur not in st:
                st.add(cur)
            else:
                return True 
            cur =cur.next
        return False