295. Where the Loop Begins
A string of fairy lights is wired as a chain of bulbs: each bulb is connected to exactly one next bulb. One careless electrician connected the last bulb back to an earlier one, so the current runs around a circuit forever after reaching it.
Given the head bulb, return the first bulb of the circuit, that is, the node where the loop starts (the node that the last bulb is wired back to). If the chain has no loop, return null. In the test data a looped chain is given as its values plus pos, the index of the loop's entry node (-1 for no loop). Do it with O(1) extra memory and without changing any link.
Example 1
- Input:
- head = {"values":[6,11,17,24,32],"pos":2}
- Output:
- 2
- Explanation:
The last node (32) links back to the node holding 17, which is where the loop starts.
Example 2
- Input:
- head = [5,10,15]
- Output:
- null
- Explanation:
No loop, so the answer is null.
Constraints
0 ≤ number of nodes ≤ 105
1 ≤ node value ≤ 105 in loop tests (values may repeat)pos 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)