leetcode：141. 环形链表【哈希表 + 快慢指针】

分析

如果用哈希表看内存位置也是可以的
但是如果要更小的内存空间的话，可以使用快慢指针
floyd判圈：如果有环，快慢指针必定相遇

算法判断：
如果head或者head.next不存在就必定没有环
然后slow从head开始，fast从head.next开始
一直看看slow和fast相等与否，用while循环，一旦相等就肯定有环
在while循环内，如果没有fast或者没有fast.next就肯定没有环了
然后slow走一步，fast走两步

ac code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next:
            return False
        
        # start
        slow, fast = head, head.next

        # if have cycle, slow and fast must meet
        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        
        return True

总结

判断链表是否有环使用快慢指针