NC4 判断链表中是否有环（python）

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


#
#
# @param head ListNode类
# @return bool布尔型
#

'''
判断给定的链表中是否有环。如果有环则返回true，否则返回false。


数据范围：链表长度 0 le n le 100000≤n≤10000，链表中任意节点的值满足 |val| <= 100000∣val∣<=100000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

输入分为2部分，第一部分为链表，第二部分代表是否有环，然后回组成head头结点传入到函数里面。-1代表无环，
其他的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编码时读入的是链表的头节点。
'''


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

        # 快慢指针初始化
        slow = head
        fast = head
        # 快慢指针逐步后移，直到最后
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            # 对后移后的快慢指针做判断，若相等则证明链表有环
            if slow == fast:
                return True
        return False


x1 = ListNode(1)
x2 = ListNode(2)
x3 = ListNode(3)
x1.next = x2
x2.next = x3
x3.next = None
a = Solution()
b = a.hasCycle(x1)
print(b)