leetcode-LL

141. Linked List Cycle.py

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        T:O(n) If there's no cycle, apparently, it's O(n). If there's cycle, O(N+K), N is non-cyclic length and K is alsmot cyclic lengh, in total is O(n).
        
        ---xxxxx
        K comes from how many iterations we needed for xxxx==it's logest distance between 2 runners / difference of speed. So, it's almost K/1
        """
        return self.detect_cycle(head)
    
    def detect_cycle(self, head):
        if not head:
            return False
        s = f = head
        while f and f.next:
            s = s.next
            f = f.next.next
            if s==f:
                return True
        return False