Does the List Loop Back?

Return true if a singly linked list contains a cycle. Otherwise return false.

You get the head of the list. A cycle means some node's next points back to an earlier node in the list. Then following next never reaches null.

• head can be null. In that case, return false.
• A single node whose next is itself is a cycle.
• The list can hold up to 100,000 nodes.
• Values can repeat. So you can't find a cycle by looking for a repeated value.
• Use only O(1) extra memory, which means a fixed amount that doesn't grow with the list. So no Set, Map or array of visited nodes. Also, don't change the nodes.