Cycle Detection in a Linked List

You are given a singly linked list with n nodes. Each node contains an integer value. In addition, you are given an integer pos which indicates the index of the node (0-indexed) that the last node is connected to. If pos is -1, then there is no cycle in the linked list.

Your task is to determine the value of the node where the cycle begins. If there is no cycle, output -1.

Note: You must solve this problem using Floyd’s Cycle Detection algorithm (also known as the tortoise and the hare algorithm). The algorithm works in two phases. In the first phase, it detects whether a cycle exists. In the second phase, if a cycle exists, it finds the entry point of the cycle.

The input is read from stdin and the answer should be printed to stdout.

inputFormat

The first line contains a single integer n indicating the number of nodes in the linked list.

The second line contains n space-separated integers representing the node values.

The third line contains an integer pos representing the index at which the cycle is connected (-1 means no cycle).

outputFormat

Output a single integer which is the value of the node where the cycle begins. If there is no cycle, output -1.

3
1 2 3
-1

-1