296. Loop Length
A merry-go-round operator links wooden horses in a chain, each horse pointing to the horse in front of it. A repair crew has hooked the last horse to an earlier one, so some of the horses now spin in a circle, while the ones before the hook-up are only a driveway into the circle.
Given the head of the chain, return the number of nodes that lie on the circle itself. If the chain ends without any loop, return 0. In the test data a looped chain is given by its values and pos, the index the last node is linked back to (-1 means no loop).
Example 1
- Input:
- head = {"values":[9,19,29,39,49,59],"pos":3}
- Output:
- 3
- Explanation:
Nodes 39, 49 and 59 form the circle, so the loop length is 3.
Example 2
- Input:
- head = [12,24]
- Output:
- 0
- Explanation:
There is no loop, so the answer is 0.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000pos is -1 or a valid index
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)