#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/linked-lists/cycle-detection-with-fast-slow

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/linked-lists/cycle-detection-with-fast-slow

Repovive

Cycle Detection with Fast-Slow - Linked Lists | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Cycle Detection with Fast-Slow

The tortoise and hare

If there's a cycle, fast and slow pointers will eventually meet inside the cycle.

slow = head
fast = head
while fast != null and fast.next != null:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return true
return false

Why do they meet? Once both pointers enter the cycle, fast gains one position on slow each step. Since the cycle has finite length, fast will eventually catch up.

If there's no cycle, fast reaches the end and the loop exits normally.

Time: $O(n)$ . Space: $O(1)$ .

You've implemented Floyd's cycle detection algorithm, one of the most famous algorithms in computer science.