Problem: Linked List Cycle Detection

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Approach: Floyd's Cycle-Finding Algorithm (Tortoise and Hare)

Instead of using a HashSet to store visited nodes ($O(n)$ space), we use two pointers moving at different speeds.

1. Initialize: slow = head, fast = head.
2. Move:
   • slow moves 1 step.
   • fast moves 2 steps.
3. Meeting Point: If there is a cycle, the fast pointer will eventually catch up to the slow pointer inside the loop.
4. No Cycle: If fast or fast.next becomes null, the list is linear.

Java Implementation

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; // Cycle detected
        }
    }
    
    return false;
}

Complexity Analysis

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