294. Chain Loop Check
A treasure map is drawn as a chain of signposts. Each signpost points at exactly one next signpost, and the last one normally points at nothing. A prankster may have bent the final signpost back toward an earlier one, trapping hikers in a loop forever.
Given the head signpost, return true if following the next links ever leads back to a signpost you have already been on, and false if the chain ends. In the test data a looped chain is described by its list of values and pos, the index of the node that the last node points back to (-1 means no loop). Aim for O(1) extra memory.
Example 1
- Input:
- head = {"values":[21,34,55,89],"pos":1}
- Output:
- true
- Explanation:
The last node (89) points back to the node holding 34, so the chain loops.
Example 2
- Input:
- head = [2,4,6,8,10]
- Output:
- false
- Explanation:
The chain simply ends after 10, so there is no loop.
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ node value ≤ 1000pos is -1 or a valid index of the chain
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)