Cycle Detection in a Linked List

Given a singly linked list with n nodes, determine whether there is a cycle in it. If a cycle exists, return the value of the node where the cycle begins. If there is no cycle, output 0.

You are expected to solve this problem using Floyd's Cycle-Finding Algorithm with a time complexity of \(O(n)\) and constant space complexity \(O(1)\). The cycle is defined by a position index where the tail of the list connects. If the given position is \(-1\), it means there is no cycle in the linked list.

Note: The position is zero-indexed. For example, if pos = 1 for a list [1, 2, 3, 4], then the tail of the list connects to the node with the value 2.

inputFormat

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

1. The first line contains an integer \(n\), the number of nodes in the linked list.
2. The second line contains \(n\) space-separated integers, representing the values of the nodes in order.
3. The third line contains an integer \(pos\), representing the position (0-indexed) where the tail should connect to form a cycle. If \(pos = -1\), then there is no cycle.

outputFormat

Output a single integer on standard output (stdout): the value of the node where the cycle begins, or 0 if there is no cycle.

## sample

3
1 2 3
-1

0

</p>