Cycle Detection in a Linked List

You are given a singly-linked list and are required to determine if the list contains a cycle. In a cycle, the last node's next pointer points back to one of the previous nodes. You are asked to implement the cycle detection using the Floyd’s Tortoise and Hare algorithm. This algorithm uses two pointers that move at different speeds. If the two pointers meet, then a cycle exists, otherwise the list has no cycle.

The time complexity of the algorithm is \(O(n)\) and the space complexity is \(O(1)\), where \(n\) is the number of nodes in the list.

inputFormat

The input is read from standard input and consists of three parts:

1. An integer n on the first line representing the number of nodes in the linked list. Note that n can be 0.
2. If n > 0, the second line contains n space-separated integers representing the node values.
3. A third line contains an integer cycle_index. If cycle_index is -1, it means there is no cycle. Otherwise, the last node is connected to the node at the given 0-indexed position, forming a cycle.

outputFormat

Output a single line to standard output: print Cycle Detected if the linked list contains a cycle, or No Cycle if it does not.

5
1 2 3 4 5
-1

No Cycle