Detect Cycle in Linked List Floyd's Algorithm in DSA Python

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs fast and the other slow. If the track loops, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, with a cycle from 5 back to 3

Goal: Detect if the linked list has a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 ->
↑slow, ↑fast (both at 1)

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> 2 -> 3 -> 4 -> 5 ->
   ↑slow
         ↑fast

Why: Slow moves one step, fast moves two steps to detect cycle faster

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

1 -> 2 -> 3 -> 4 -> 5 ->
      ↑slow
               ↑fast

Why: Pointers continue moving; fast pointer moves twice as fast

Step 4: Move slow by 1 step to node 4, fast moves 2 steps but cycles back to node 4

1 -> 2 -> 3 -> 4 -> 5 ->
           ↑slow
           ↑fast

Why: Fast pointer loops back due to cycle; slow pointer approaches fast

Step 5: Slow and fast pointers meet at node 4, cycle detected

1 -> 2 -> 3 -> 4 -> 5 ->
           ↑slow, ↑fast (meeting point)

Why: Meeting point confirms presence of cycle

Result:

1 -> 2 -> 3 -> 4 -> 5 -> (cycle back to 3)
Cycle detected: True

Annotated Code

DSA Python

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

def detect_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next  # move slow by 1
        fast = fast.next.next  # move fast by 2
        if slow == fast:
            return True  # cycle detected
    return False  # no cycle

# Create linked list 1->2->3->4->5 with cycle from 5 to 3
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head.next.next  # cycle here

print("Cycle detected:", detect_cycle(head))

slow = slow.next # move slow by 1

advance slow pointer by one node

fast = fast.next.next # move fast by 2

advance fast pointer by two nodes

if slow == fast:

check if pointers meet indicating a cycle

return True # cycle detected

return true when cycle is found

Output

Cycle detected: True

Complexity Analysis

Time: O(n) because both pointers traverse the list at most once until they meet or reach the end

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to track visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient

Edge Cases

empty list (head is None)

function returns False immediately as there is no cycle

DSA Python

while fast and fast.next:

single node without cycle

function returns False as fast.next is None

DSA Python

while fast and fast.next:

two nodes with cycle (second node points back to first)

function detects cycle when slow and fast meet

DSA Python

if slow == fast:

When to Use This Pattern

When you need to detect a cycle in a linked list efficiently, Floyd's algorithm is the go-to pattern because it uses two pointers moving at different speeds to find a loop without extra space.

Common Mistakes

Mistake: Moving fast pointer by one step instead of two
Fix: Advance fast pointer by two steps to ensure faster traversal and correct cycle detection

Mistake: Not checking if fast or fast.next is None before moving pointers
Fix: Add condition 'while fast and fast.next' to avoid runtime errors

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use it when you want to find loops in linked lists efficiently without extra memory.

The key insight is that a fast pointer will eventually catch a slow pointer if a cycle exists.