Detect a Loop in a Linked List

Problem

Determine whether a singly linked list contains a cycle, using O(1) extra space, and return the node where the cycle begins (or null if there is none).

Input / Output

• Input: the head of a singly linked list.
• Output: the node where the cycle starts, or null if the list is acyclic.

Constraints

• 0 ≤ nodes ≤ 10^4
• O(1) extra space.

Example

1→2→3→4→2 (node 4 links back to 2) -> cycle starts at node 2
1→2→3→null                         -> no cycle