Linked List Cycle
Easy · linked list
A chain of numbered stations is stored in an array. Station 0 is where you start. nxt[i] is the station that station i sends you on to, or -1 if station i is the last one and the trip ends there.
Follow the links from station 0. Return true if the trip never ends because you eventually arrive at a station you have already been to, and false if you reach a station whose link is -1.
Only stations you can actually reach from station 0 matter. Other stations may form loops of their own, and those do not count. If nxt is empty there is nothing to follow, so the answer is false. A station may link to itself.
Examples
Example 1
Input: nxt = [1, 2, 3, -1]
Output: false
The trip goes 0, 1, 2, 3 and stops at station 3 because its link is -1.
Example 2
Input: nxt = [1, 2, 3, 1]
Output: true
The trip goes 0, 1, 2, 3 and then back to 1, which has already been visited, so it circles forever.
Example 3
Input: nxt = [-1, 2, 1]
Output: false
Stations 1 and 2 loop between themselves, but station 0 ends the trip immediately and never gets there.
Constraints
- 0 <= len(nxt) <= 10^4
- Each nxt[i] is either -1 or a station number in the range 0 to len(nxt) - 1.