Big O Gym › Problem

Big O Practice: Detect Cycle Floyd

Time and space complexity practice in Python and JavaScript. Concept tested: tortoise-and-hare meets in O(n).

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Variables

  • n - number of nodes in the list

Explanation

The fast pointer moves twice per step; if a cycle exists, the gap between fast and slow shrinks by one each round - they meet within **O(n)** steps. Two pointers only, **O(1)** space. The hash-set alternative is O(n) space.

More Big O practice problems · Today's daily problem