306. Detect a Cycle in a Linked List (Floyd's Algorithm)

Given the head of a singly linked list, determine if the list contains a cycle.

A cycle exists if a node's next pointer points back to a previous node in the list, forming a loop. Return true if a cycle exists, otherwise return false.

You must solve it using O(1) extra space.

Input: A singly linked list represented as an array of values, and an integer pos (0-indexed) indicating which node the tail connects to (-1 if no cycle).

Output: Boolean true if cycle detected, false otherwise.

Examples

Input: [3,2,0,-4], pos=1
Output: true
Explanation: The tail node (-4) points back to node at index 1 (value=2), forming a cycle.
Floyd's: slow and fast pointers will eventually meet inside the cycle.

Input: [1,2], pos=0
Output: true
Explanation: The tail (node 2) points back to node at index 0 (node 1). Cycle exists.

Input: [1], pos=-1
Output: false
Explanation: Single node, no cycle. fast becomes NULL immediately. Return false.

Constraints

• 0 <= number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid 0-indexed node position

Asked by