"""
方法二: 快慢指针(龟兔赛跑算法 / Floyd 判圈算法)

解题思路：
假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。
当「乌龟」和「兔子」从链表上的同一个节点开始移动时：
如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方，直到「兔子」跑完全程；
如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈

定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。
初始时，慢指针在位置 head，而快指针在位置 head.next。
这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表


复杂度分析：
时间复杂度：O(n)，其中 n 是链表的节点数量：
    当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次，共 n + m 次(m 为慢指针已访问的节点数)。
    当链表中存在环时，当慢指针也进入环时，快指针就可以反过来追上慢指针了。在环内，快慢指针的距离将每次减小一。极端情况下环长为 n，所以最多 n 次就能追上慢指针。

空间复杂度：O(1)。我们只使用了两个指针的额外空间
"""


# 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

        # 为什么不是像「龟兔赛跑算法」中那样在同一个节点开始移动呢？
        # 因为 while 循环的循环条件先于循环体，由于循环条件一定是判断快慢指针是否重合，
        # 如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。
        # 因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，
        # 这样我们就可以使用 while 循环了。
        # 或者，使用 do-while 循环。此时，我们就可以把快慢指针的初始值都置为 head
        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:  # 快指针遍历完整个链表了，也没有与慢指针相遇
                return False
            slow = slow.next  # 慢指针每次只移动一步
            fast = fast.next.next  # 快指针每次移动两步

        return True
