DSA Interview Prep · Lesson

Cycle Detection with Floyd's Algorithm

Detect cycles using the slow-fast pointer approach, find the entry point of the cycle, and prove the algorithm's correctness mathematically.

What Is a Cycle in a Linked List?

A cycle in a linked list occurs when a node's next pointer points back to a previously visited node, creating an infinite loop. Traversing such a list with a while head loop would run forever. Cycle detection is a classic interview problem and the foundation of more advanced pointer algorithms.

The naive approach stores every visited node in a set and checks for membership — O(n) time, O(n) space. Floyd's algorithm solves the same problem in O(n) time and O(1) space, which is what interviewers expect.

Floyd's Slow-Fast Pointer Algorithm

Floyd's cycle detection (the 'tortoise and hare') uses two pointers: slow advances one step at a time, fast advances two steps. If no cycle exists, fast reaches None first. If a cycle exists, fast eventually laps slow inside the cycle and they meet at the same node. The meeting proves a cycle exists.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

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

# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
    nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1]   # cycle: -4 -> 2

print(hasCycle(nodes[0]))  # True

All lessons in this course

← Back to DSA Interview Prep