Does the List Have a Cycle?

Return True if the list has a cycle, that is, if following next pointers from head never reaches None.

A list can have a cycle: the last node's next points back at an earlier node. The tests give such a list as {"values": [...], "cycle": k}, where the last node points back at node k (counting from 0), and k = -1 means no cycle.

The starter code remembers every visited node in a list. It is correct but too slow. Use O(1) memory.

Examples

Example 1

Input:

has_cycle(head)  # head = 3 -> 2 -> 0 -> -4, and -4 points back at 2

Output:

True

Example 2

Input:

has_cycle(head)  # head = 1 -> 2, no cycle

Output:

False

Constraints

• 0 <= number of nodes <= 100000
• The cycle position k is -1 or a valid index.