leetcode：141. Circular linked list [hash table + speed pointer]

analysis

It is also possible to use a hash table to see the memory location
But if you want smaller memory space , You can use the speed pointer
floyd Judge circle ： If there are rings , The fast and slow pointers must meet

Algorithm judgment ：
If head perhaps head.next If there is no ring, there must be no ring
then slow from head Start ,fast from head.next Start
Keep looking slow and fast Equal or not , use while loop , Once equal, there must be a ring
stay while Within the loop , without fast Or not fast.next There must be no ring
then slow Take a step ,fast Take two steps

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

summary

Judge whether the linked list has a ring and use the speed pointer