linked-list
two-pointers
cycle-detection
An array nextIndices describes a linked list whose head is node 0; each value is the next node's index, or -1 for null. If the list has a cycle, return the index of the node where the cycle begins. If there is no cycle, return -1.
Do not modify the list — treat nextIndices as read-only, the same encoding used by linked-list-cycle.
Input / output
- Input:
nextIndices: int[] - Output:
int, the index where the cycle begins, or-1
Constraints
- 0 <= nextIndices.length <= 10,000
- Every entry is
-1or a valid index intonextIndices - Following indices from 0 either reaches
-1or eventually repeats an index (a genuine cycle)
Follow-up
Can you solve it using O(1) extra space (Floyd's cycle-detection / tortoise-and-hare), without a visited-set?
Examples
Example 1
Input: nextIndices = [1,2,0,-1]
Output: 0
Example 2 (no cycle)
Input: nextIndices = [1,-1]
Output: -1
Example 3 (single node, no cycle)
Input: nextIndices = [-1]
Output: -1
🔒 6 hidden
Running will execute all 9 cases, including 6 hidden ones.