Linked ListFast and Slow Pointers
Decide whether a linked list contains a cycle, meaning some node can be reached again by following next pointers. Do it in O(1) extra space. The values are given as an array; build the linked list from them yourself, then solve it with pointers. The last node's next pointer connects to the node at index pos (0-based), or to nothing if pos is -1.
Input
Line 1: n. Line 2: the n node values. Line 3: pos, the index the tail connects back to, or -1 for no cycle.
Output
Print true if the list has a cycle, otherwise false.
Constraints
1 <= n <= 10^4 -1 <= pos < n
Example 1
Input
4 3 2 0 -4 1
Output
true
The tail connects back to the node at index 1.
Example 2
Input
2 1 2 -1
Output
false
No node points backwards.