Find the Start of the Cycle in a Singly Linked List

You are given a singly linked list which may contain a cycle. Your task is to determine the value of the node at which the cycle begins. If there is no cycle in the list, output 0.

The linked list is constructed from n nodes with given integer values. The list may have a cycle: an integer k is given representing the index (0-indexed) of the node that the tail node should point to. If k = -1, then there is no cycle in the list.

The solution typically relies on Floyd's Cycle Detection Algorithm (also known as the Tortoise and Hare algorithm). In particular, if a cycle exists, after the meeting point of the two pointers, moving one pointer to the head and then advancing both pointers at the same pace will eventually lead them to meet again at the start of the cycle. Mathematically, if the distance from the head to the cycle start is \( k \) and the meeting point is \( m \) steps inside the cycle, the technique ensures that they meet again at the cycle start.

inputFormat

The input is read from standard input and has the following format:

n
v1 v2 v3 ... vn
k

Here,

• n is the number of nodes in the linked list.
• v1, v2, ..., vn are the integer values of the nodes.
• k is an integer indicating the 0-indexed position of the node where the cycle begins. If k is -1, it means there is no cycle.

outputFormat

Output the value of the node where the cycle starts. If there is no cycle, output 0. The output is printed to standard output.

## sample

5
1 2 3 4 5
-1

0

</p>