Linked List Loop

Given the head of a singly linked list, determine whether the list contains a cycle. A cycle exists if, by repeatedly following the next pointer, you eventually revisit a node that was already visited (i.e., some node's next pointer points back to an earlier node in the list rather than to None).

Return True if there is a cycle, and False otherwise. You must solve this using O(1) extra space.

Example 1

Input: a list where node values are 3 -> 2 -> 0 -> -4, and the last node's next points back to the node with value 2.

Output: True

Explanation: starting from the tail, following next leads back to the node valued 2, forming a cycle.

Example 2

Input: 1 -> 2, where 2.next is None.

Output: False

Explanation: the list terminates normally with no cycle.

Constraints

• The number of nodes is in the range [0, 10^4].
• Node values are arbitrary integers (not necessarily unique, and not useful for detecting the cycle).
• You should not modify the list or use additional data structures proportional to the input size.