Detect a Cycle in a Linked List

Problem Determine whether a singly linked list contains a cycle, using O(1) extra space. If a cycle exists, also return the node where the cycle begins.

Input / Output

• Input: the head of a singly linked list.
• Output: whether a cycle exists, and if so the node where it starts.

Constraints

• 0 <= number of nodes <= 10^4.
• O(1) auxiliary space (a hash set of visited nodes is the easy O(n)-space baseline to beat).

Example

• A list whose tail points back to the 2nd node has a cycle starting at node 2; a nil-terminated list has none.