297. Linked List Cycle

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Detect whether a linked list contains a cycle using Floyd's Tortoise and Hare algorithm — a two-pointer technique where one pointer moves twice as fast as the other.

Requirements

1. Basic Functionality

• Return true if the list has a cycle, false otherwise
• Must use O(1) extra space (no hash set)
• Handle empty lists and single nodes

Example Usage

// List: 3 → 2 → 0 → -4 → (back to 2)  →  true
// List: 1 → 2 → null                    →  false

Real-World Context

• Deadlock detection: Finding circular waits in operating systems
• Infinite loop detection: Detecting cycles in state machines or workflows
• Garbage collection: Identifying circular references in memory management