Linked List Cycle Detection

Problem Given the head of a singly linked list, determine whether the list contains a cycle, and — as the natural extension — return the node at which the cycle begins.

Input / Output

• Input: head, the first node of a singly linked list (possibly null).
• Output: boolean for the detection variant; the cycle's entry node (or null) for the locate variant.

Constraints

• Up to 10^4 nodes.
• Must run in O(1) extra space — a visited hash set is the obvious O(n)-space answer and is usually ruled out.
• The list may not be modified (no node marking or pointer reversal).

Example

• 3 -> 2 -> 0 -> -4, with -4 pointing back to 2: cycle exists, entry node is 2.
• 1 -> 2 -> null: no cycle.
• Tricky cases: a single node pointing to itself (cycle, entry = head), and an empty list (no cycle).