🐢🐇 Cycle Detection - Floyd's Algorithm

Intermediate ~25 min read ⭐ Top Interview Question

Imagine a linked list where the last node points back to an earlier node instead of null - creating an infinite loop! Floyd's Tortoise and Hare algorithm detects this in O(n) time with O(1) space. This elegant solution appears frequently at Google, Amazon, Microsoft, and Facebook!

🎯 Interview Alert!

Floyd's algorithm is a MUST-KNOW:

✅ Google - Common question
✅ Amazon - Frequently asked
✅ Microsoft - Standard interview
✅ Facebook - Regular appearance
✅ LinkedIn - Popular question

The O(1) space solution is what separates good from great!

The Problem

Detect if a linked list has a cycle

Example WITH cycle:

1 → 2 → 3 → 4 → 5
        ↑           ↓
        └───────────┘
        
Cycle exists! Node 5 points back to node 3

Example WITHOUT cycle:

1 → 2 → 3 → 4 → 5 → null

No cycle - ends with null

Challenge: Detect cycle in O(1) space (no HashSet!)

Floyd's Tortoise and Hare 🐢🐇

The brilliant insight: Use two pointers moving at different speeds!

The Algorithm

def has_cycle(head):
    slow = head  # 🐢 Tortoise - moves 1 step
    fast = head  # 🐇 Hare - moves 2 steps
    
    while fast and fast.next:
        slow = slow.next      # Move 1 step
        fast = fast.next.next # Move 2 steps
        
        if slow == fast:
            return True  # They met - cycle!
    
    return False  # Hare reached end - no cycle

That's it! Just 9 lines to detect cycles.

See It in Action

Watch the tortoise and hare move through the list:

Why It Works

💡 The Race Track Analogy

Think of a circular race track:

🐢 Tortoise runs at 1 mph
🐇 Hare runs at 2 mph (twice as fast!)
If the track is circular, the hare will eventually lap the tortoise
They MUST meet at some point!

Same with linked lists: If there's a cycle, fast will catch slow!

Step-by-Step Example

Let's trace through a list with a cycle:

List structure:

1 → 2 → 3 → 4 → 5
        ↑           ↓
        └───────────┘

Step 0: Both start at node 1

🐢🐇 at 1

Step 1: Slow moves to 2, Fast moves to 3

🐢 at 2, 🐇 at 3

Step 2: Slow moves to 3, Fast moves to 5

🐢 at 3, 🐇 at 5

Step 3: Slow moves to 4, Fast moves to 4 (via cycle!)

🐢 at 4, 🐇 at 4 → They met! Cycle detected!

Finding the Cycle Start

Once we know there's a cycle, where does it start?

The Magic Trick

def find_cycle_start(head):
    # Step 1: Detect cycle and find meeting point
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break  # Found meeting point
    else:
        return None  # No cycle
    
    # Step 2: Find cycle start
    slow = head  # Move slow to head
    
    while slow != fast:
        slow = slow.next  # Both move 1 step
        fast = fast.next
    
    return slow  # This is the cycle start!

Why Does This Work?

💡 The Mathematics

Let's define:

x = distance from head to cycle start
y = distance from cycle start to meeting point
C = cycle length

When they meet:

Slow traveled: x + y
Fast traveled: x + y + nC (n complete cycles)
Fast = 2 × Slow (twice the distance)

Therefore:

x + y + nC = 2(x + y)
x + y + nC = 2x + 2y
nC = x + y
x = nC - y

This means: Distance from head to cycle start (x) equals distance from meeting point to cycle start (nC - y)!

So: If we move both pointers at same speed, they meet at cycle start!

The Complete Code

"""
Linked List Cycle Detection - Floyd's Tortoise and Hare Algorithm
Detect, find start, and remove cycles in O(n) time, O(1) space
Another top interview question!
"""

class Node:
    """Node in a singly linked list"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """Linked List with cycle detection operations"""
    def __init__(self):
        self.head = None
    
    def insert_at_tail(self, data):
        """Insert at end"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return new_node
        
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        return new_node
    
    def create_cycle(self, pos):
        """Create cycle for testing - tail points to node at position pos"""
        if not self.head or pos < 0:
            return
        
        # Find tail and node at position
        tail = self.head
        cycle_node = None
        current = self.head
        index = 0
        
        while current:
            if index == pos:
                cycle_node = current
            if not current.next:
                tail = current
                break
            current = current.next
            index += 1
        
        if cycle_node:
            tail.next = cycle_node
            print(f"✓ Created cycle: tail → node at position {pos} (value={cycle_node.data})")
    
    def has_cycle(self):
        """
        Floyd's Cycle Detection - THE TORTOISE AND HARE!
        Time: O(n), Space: O(1)
        """
        print("\n🐢🐇 Floyd's Algorithm: Tortoise and Hare")
        print("Tortoise moves 1 step, Hare moves 2 steps")
        print("If they meet, there's a cycle!")
        
        if not self.head:
            return False
        
        slow = self.head  # Tortoise 🐢
        fast = self.head  # Hare 🐇
        
        step = 0
        while fast and fast.next:
            slow = slow.next        # Move 1 step
            fast = fast.next.next   # Move 2 steps
            step += 1
            
            print(f"\nStep {step}:")
            print(f"  🐢 Tortoise at: {slow.data}")
            print(f"  🐇 Hare at: {fast.data if fast else 'None'}")
            
            if slow == fast:
                print(f"\n✅ CYCLE DETECTED! They met at node {slow.data}")
                return True
        
        print("\n✅ NO CYCLE - Hare reached the end")
        return False
    
    def find_cycle_start(self):
        """
        Find where the cycle starts
        Time: O(n), Space: O(1)
        """
        print("\n🔍 Finding cycle start...")
        
        if not self.head:
            return None
        
        # Step 1: Detect cycle and find meeting point
        slow = self.head
        fast = self.head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                print(f"✓ Cycle detected, meeting point: {slow.data}")
                break
        else:
            print("✗ No cycle found")
            return None
        
        # Step 2: Find cycle start
        # Move one pointer to head, keep other at meeting point
        # Move both at same speed - they'll meet at cycle start!
        print("\n🎯 Finding cycle start:")
        print("  Moving one pointer to HEAD")
        print("  Moving both at same speed...")
        
        slow = self.head
        step = 0
        
        while slow != fast:
            slow = slow.next
            fast = fast.next
            step += 1
            print(f"  Step {step}: slow={slow.data}, fast={fast.data}")
        
        print(f"\n✅ Cycle starts at: {slow.data}")
        return slow
    
    def get_cycle_length(self):
        """
        Get length of the cycle
        Time: O(n), Space: O(1)
        """
        if not self.head:
            return 0
        
        # Detect cycle
        slow = self.head
        fast = self.head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                # Found cycle, now count length
                length = 1
                current = slow.next
                
                while current != slow:
                    length += 1
                    current = current.next
                
                print(f"✓ Cycle length: {length} nodes")
                return length
        
        return 0
    
    def remove_cycle(self):
        """
        Remove cycle from linked list
        Time: O(n), Space: O(1)
        """
        print("\n🔧 Removing cycle...")
        
        if not self.head:
            return
        
        # Find cycle start
        slow = self.head
        fast = self.head
        
        # Detect cycle
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                break
        else:
            print("✗ No cycle to remove")
            return
        
        # Find cycle start
        slow = self.head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        cycle_start = slow
        print(f"✓ Cycle starts at: {cycle_start.data}")
        
        # Find node before cycle start (in the cycle)
        while fast.next != cycle_start:
            fast = fast.next
        
        # Break the cycle
        print(f"✓ Breaking link: {fast.data}.next = null")
        fast.next = None
        print("✅ Cycle removed!")
    
    def print_list(self, max_nodes=20):
        """Print list (with limit to avoid infinite loop if cycle exists)"""
        if not self.head:
            print("List: (empty)")
            return
        
        current = self.head
        elements = []
        count = 0
        
        while current and count < max_nodes:
            elements.append(str(current.data))
            current = current.next
            count += 1
        
        if count == max_nodes and current:
            elements.append("... (cycle or long list)")
        
        print(f"List: {' → '.join(elements)}")

# Example 1: Detect Cycle
print("=" * 70)
print("Example 1: Floyd's Cycle Detection Algorithm")
print("=" * 70)

ll = LinkedList()
for val in [1, 2, 3, 4, 5, 6]:
    ll.insert_at_tail(val)

print("\nList without cycle:")
ll.print_list()
ll.has_cycle()

print("\n" + "─" * 70)
print("Creating cycle: tail → node at position 2 (value=3)")
print("─" * 70)

ll.create_cycle(2)  # Create cycle: 6 → 3

print("\nList with cycle:")
print("1 → 2 → 3 → 4 → 5 → 6")
print("        ↑           ↓")
print("        └───────────┘")

ll.has_cycle()

# Example 2: Find Cycle Start
print("\n" + "=" * 70)
print("Example 2: Find Where Cycle Starts")
print("=" * 70)

ll2 = LinkedList()
for val in [10, 20, 30, 40, 50]:
    ll2.insert_at_tail(val)

ll2.create_cycle(1)  # Cycle at position 1 (value=20)

print("\nList structure:")
print("10 → 20 → 30 → 40 → 50")
print("     ↑                ↓")
print("     └────────────────┘")

ll2.find_cycle_start()

# Example 3: Cycle Length
print("\n" + "=" * 70)
print("Example 3: Get Cycle Length")
print("=" * 70)

ll3 = LinkedList()
for val in [1, 2, 3, 4, 5]:
    ll3.insert_at_tail(val)

ll3.create_cycle(2)  # Cycle: 5 → 3

print("\nList structure:")
print("1 → 2 → 3 → 4 → 5")
print("        ↑       ↓")
print("        └───────┘")

ll3.get_cycle_length()

# Example 4: Remove Cycle
print("\n" + "=" * 70)
print("Example 4: Remove Cycle")
print("=" * 70)

ll4 = LinkedList()
for val in [100, 200, 300, 400]:
    ll4.insert_at_tail(val)

ll4.create_cycle(1)

print("\nBefore removing cycle:")
print("Has cycle:", ll4.has_cycle())

ll4.remove_cycle()

print("\nAfter removing cycle:")
ll4.print_list()
print("Has cycle:", ll4.has_cycle())

# Visual Explanation
print("\n" + "=" * 70)
print("How Floyd's Algorithm Works")
print("=" * 70)

print("\nWHY IT WORKS:")
print("─" * 70)
print("If there's a cycle:")
print("  • Slow pointer (🐢) moves 1 step at a time")
print("  • Fast pointer (🐇) moves 2 steps at a time")
print("  • Fast will eventually 'lap' slow inside the cycle")
print("  • They MUST meet if cycle exists!")

print("\nIf there's NO cycle:")
print("  • Fast pointer reaches end (null)")
print("  • They never meet")

print("\n" + "=" * 70)
print("Finding Cycle Start - The Math")
print("=" * 70)

print("\nGiven:")
print("  • Distance from head to cycle start = x")
print("  • Distance from cycle start to meeting point = y")
print("  • Cycle length = C")

print("\nWhen they meet:")
print("  • Slow traveled: x + y")
print("  • Fast traveled: x + y + nC (n = number of cycles)")
print("  • Fast = 2 × Slow")
print("  • Therefore: x + y + nC = 2(x + y)")
print("  • Simplify: x = nC - y")

print("\nSo if we:")
print("  1. Move one pointer to head")
print("  2. Move both at same speed")
print("  3. They meet at cycle start!")

# Complexity Analysis
print("\n" + "=" * 70)
print("Complexity Analysis")
print("=" * 70)
print(f"{'Operation':<30} {'Time':<15} {'Space':<15}")
print("-" * 70)
print(f"{'Detect cycle':<30} {'O(n)':<15} {'O(1) ✓':<15}")
print(f"{'Find cycle start':<30} {'O(n)':<15} {'O(1) ✓':<15}")
print(f"{'Get cycle length':<30} {'O(n)':<15} {'O(1) ✓':<15}")
print(f"{'Remove cycle':<30} {'O(n)':<15} {'O(1) ✓':<15}")

print("\nAlternative: Using HashSet")
print(f"{'Detect with HashSet':<30} {'O(n)':<15} {'O(n)':<15}")
print("✗ Not optimal - uses extra space!")

# Interview Tips
print("\n" + "=" * 70)
print("Interview Tips")
print("=" * 70)
print("✅ Floyd's algorithm is THE standard solution")
print("✅ Always mention O(1) space - key advantage!")
print("✅ Draw the cycle to visualize")
print("✅ Explain tortoise and hare analogy")
print("✅ Handle edge cases: empty list, no cycle, single node")

print("\n" + "=" * 70)
print("Common Interview Variations")
print("=" * 70)
print("1. Detect if cycle exists ✓ (covered)")
print("2. Find cycle start ✓ (covered)")
print("3. Find cycle length ✓ (covered)")
print("4. Remove cycle ✓ (covered)")
print("5. Find intersection of two lists (similar technique!)")

print("\n" + "=" * 70)
print("Key Takeaways")
print("=" * 70)
print("✓ Floyd's algorithm: slow (1 step) + fast (2 steps)")
print("✓ If cycle exists, they WILL meet")
print("✓ O(n) time, O(1) space - optimal!")
print("✓ Can find start, length, and remove cycle")
print("✓ Top interview question at FAANG companies!")

Output

Click Run to execute your code

Complexity Analysis

Operation	Time	Space	Notes
Detect cycle	O(n) ✓	O(1) ✓✓	Floyd's algorithm
Find cycle start	O(n) ✓	O(1) ✓✓	Two-phase approach
Get cycle length	O(n) ✓	O(1) ✓✓	Count after detection
Remove cycle	O(n) ✓	O(1) ✓✓	Find start, break link
Using HashSet	O(n)	O(n)	Not optimal!

Common Mistakes

❌ Mistake #1: Not Checking fast.next

# WRONG - crashes if fast.next is null!
while fast:
    fast = fast.next.next  # Crashes!

# RIGHT - check both fast and fast.next
while fast and fast.next:
    fast = fast.next.next  # Safe!

❌ Mistake #2: Moving Both Same Speed

# WRONG - both move 1 step
slow = slow.next
fast = fast.next  # They'll never meet!

# RIGHT - fast moves 2 steps
slow = slow.next
fast = fast.next.next  # Twice as fast!

❌ Mistake #3: Using Extra Space

# WRONG - uses O(n) space
visited = set()
while current:
    if current in visited:
        return True
    visited.add(current)

# RIGHT - O(1) space with Floyd's
# (Use the algorithm above!)

Interview Variations

Common Follow-ups

Detect if cycle exists ✓ (covered)
Find where cycle starts ✓ (covered)
Find length of cycle ✓ (covered)
Remove the cycle ✓ (covered)
Find intersection of two lists (similar technique!)
Check if list is palindrome (uses slow/fast pointers)

Interview Tips

💡 How to Ace This Question

✅ Explain the analogy: "Like a race track - faster runner laps slower"
✅ Draw it out: Visualize the cycle and pointer movements
✅ Mention O(1) space: This is the key advantage over HashSet!
✅ Handle edge cases: Empty list, single node, no cycle
✅ Explain the math: Show you understand WHY it works
✅ Know the variations: Finding start, length, removal

✅ What Interviewers Want to See

Understanding of two-pointer technique
Ability to optimize space complexity
Knowledge of mathematical reasoning
Handling edge cases properly
Clear communication of algorithm

Real-World Applications

Where Is This Used?

Deadlock detection: Finding circular dependencies
Memory leak detection: Circular references
Graph algorithms: Detecting cycles in graphs
Duplicate detection: Finding repeated sequences
Infinite loop detection: Program analysis

Summary

Floyd's Tortoise and Hare

Use two pointers: slow (1 step) and fast (2 steps)
If cycle exists: They will meet inside the cycle
If no cycle: Fast reaches null
To find start: Move one to head, both move 1 step, meet at start
O(n) time, O(1) space: Optimal solution!

Interview tip: This is a classic two-pointer problem. The key insight is using different speeds to detect cycles. Always explain the race track analogy - it shows deep understanding!

What's Next?

You've mastered cycle detection! Next: Two Pointer Techniques - finding middle, nth from end, and palindrome checking!

Practice: Try implementing all 4 operations (detect, find start, get length, remove). Draw cycles on paper to visualize!

Previous Linked List Reversal

Next Two Pointer Techniques