Problem

At Slack, a service may receive malformed linked-list structures from an in-memory cache. Write a function that determines whether a singly linked list contains a cycle.

A cycle exists if following next pointers eventually revisits a previously seen node instead of reaching None.

Formal Specification

Implement a function that takes the head of a singly linked list and returns a boolean:

• Input: head, the first node of a singly linked list, or None
• Output: True if the list contains a cycle, otherwise False

Each node has:

• val: integer value
• next: reference to the next node or None

Examples

Example 1

Input: 3 -> 2 -> 0 -> -4, tail connects to node with value 2
Output: True

Explanation: After reaching -4, the list points back to the node with value 2, creating a loop.

Example 2

Input: 1 -> 2 -> None
Output: False

Explanation: Traversal reaches None, so no cycle exists.

Constraints

• Number of nodes is in the range [0, 10^5]
• -10^9 <= node.val <= 10^9
• The list may be empty
• Aim for O(1) extra space if possible