A conveyor is modeled as a singly linked list of n nodes indexed 0..n-1 from the head. Normally the last node points to nothing, but a maintenance splice may connect the tail's next back to an earlier node, creating an endless loop. You are told the 0-indexed node the tail connects to, or -1 if the tail connects to nothing.
Decide whether following next pointers from the head ever revisits a node (a cycle).
Line 1: an integer n, the number of nodes.
Line 2: n space-separated integers, the node values from head to tail (empty line when n is 0).
Line 3: an integer target. If target == -1 the tail points to nothing; otherwise 0 <= target <= n-1 and the tail's next is set to the node at index target.
Print YES if the list contains a cycle, otherwise print NO.
target == -1, or 0 <= target <= n-1n == 0, target is -1.Example 1
Input
4 3 2 0 -4 1
Expected
YES
Explanation
The tail (index 3) is spliced back to index 1, so walking next from the head cycles between indices 1,2,3 forever. Output YES.
Example 2
Input
3 1 2 3 -1
Expected
NO
Explanation
target is -1, so the tail ends the list. Traversal terminates without repeating a node. Output NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →