Detect a Loop in Linked List (Floyd Cycle Detection)

Detect a Loop in Linked List (Floyd Cycle Detection)

This guide explains the intuition, optimized approach, and Java implementation for detect a loop in linked list (floyd cycle detection), with practical tips for interviews and production coding standards.

Problem

Determine whether a linked list contains a cycle.

Approach: Slow and Fast Pointers

• slow moves one step
• fast moves two steps
• If there is a cycle, they must meet
• If fast reaches null, no cycle exists

Java Solution

class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
}

Complexity

• Time: O(n)
• Space: O(1)

Why This Is Better Than HashSet

HashSet approach works but uses extra memory O(n). Floyd’s algorithm gives constant-space detection.

Key Takeaways

• Start from the brute-force idea, then derive the optimized invariant.
• Use clean pointer/index boundaries to avoid off-by-one bugs.
• Validate against edge cases (empty input, single element, duplicates, extreme values).