Detect the entry of a linked-list cycle
Connect the tail to the node at zero-based pos, or leave it null for pos=-1. Print the cycle entry index, or -1 when acyclic; find it with Floyd's algorithm. Follow the stated ordering and edge-case conventions exactly. Interviewers use this task to probe algorithm selection, invariants, and boundary handling.
Input
n, n integer node values, then pos.
Output
Connect the tail to the node at zero-based pos, or leave it null for pos=-1. Print the cycle entry index, or -1 when acyclic; find it with Floyd's algorithm.
Constraints
0 <= n <= 100000; values in [-1000000000,1000000000]; pos=-1 or 0 <= pos<n; n=0 requires pos=-1.
Example
Input
4 3 2 0 -4 1
Output
1
Example 2 input
5 1 1 1 1 1 0
Output
0
This example exercises a further boundary or ordering case.
Public test cases (2)
Input
4 3 2 0 -4 1
Expected output
1
Input
3 1 2 3 -1
Expected output
-1
Hints (2)
- Identify the state needed to avoid recomputing work for each element.
- Move pointers at different speeds; after a meeting, move one pointer from the head to locate the entry.
Target complexity: time O(n) · space O(1) auxiliary for detection; O(n) construction