Linked List Cycle

Problem

You are given the head of a singly linked list. Determine whether the list contains a cycle, meaning that following next pointers from the head eventually revisits a node instead of reaching None. Return true if a cycle exists and false otherwise. Aim for constant extra space.

• The list contains between 0 and 20,000 nodes.
• Node values fit in a signed 32-bit integer.
• Values may repeat, so you cannot detect a cycle by comparing values.

Examples

• 7 -> 11 -> 4 -> 9, and 9 points back to 11 → true. Following next from the head loops through 11, 4, 9 forever.
• 2 -> 4 -> 6 -> 8, and 8 points to None → false. The walk terminates.
• 6 with next = None → false. A single node with no back-pointer is acyclic.

Hints

1. Recording every visited node in a set works but costs O(n) memory. Can you detect "I have been here before" without remembering everything?
2. Imagine two runners on a circular track at different speeds. Do they ever meet?
3. Advance a slow pointer by one and a fast pointer by two. If the fast pointer reaches None, there is no cycle; if it ever equals the slow pointer, there is.