Cycle Detection in a Linked List using Floyd's Algorithm

Given a linked list represented by an array of integers, where each element indicates the next node index (1-indexed) and a value of -1 indicates the end of the list, determine whether a cycle exists in the list. If a cycle exists, output the 1-based index of the first node in the cycle; otherwise, output "No cycle".

This problem can be solved using Floyd's Tortoise and Hare algorithm. The core idea is to use two pointers moving at different speeds to determine if a cycle exists. Once a cycle is detected, reset one pointer to the beginning of the list and then move both pointers at the same speed. The point at which they meet is the start of the cycle.

In mathematical terms, if we denote the progression function as $$ f(i) = \begin{cases} edges[i]-1, &\text{if } edges[i] \neq -1 \ -1, &\text{if } edges[i] = -1 \end{cases} $$ , then the algorithm finds an index ( i ) such that repeated application of ( f ) forms a cycle.

inputFormat

The input is given via standard input (stdin) in the following format:

Line 1: An integer ( n ) representing the number of nodes in the linked list.
Line 2: ( n ) space-separated integers representing the edges of the linked list. Each integer is either a positive integer (the next node's 1-based index) or -1 indicating the end of the list.

outputFormat

Print the result to standard output (stdout). If the linked list contains a cycle, output the 1-based index of the first node in the cycle. Otherwise, output the string "No cycle".## sample

5
2 3 4 5 -1

No cycle