Detecting Loops in a Linked List

You are given a linked list with n nodes. The linked list is described by two lines after the first input line. The first line after n contains n space-separated integers representing the values of the nodes, and the next line contains a single integer k representing the index (0-indexed) of the node that the last node points to. If k is -1, then no loop is created in the list.

Your task is to detect if there is a loop in the linked list. A loop occurs when a node's next pointer does not point to null but instead points to a previous node in the list, forming a cycle. You should output True if there is a loop and False otherwise.

The efficient solution uses Floyd’s cycle detection algorithm (also known as the tortoise and hare algorithm) to determine if a cycle exists in the list.

In mathematical terms, if we denote the linked list as a sequence of nodes \( n_0, n_1, n_2, \dots, n_{m-1} \) and if the last node points to node \( n_k \) (where \( 0 \le k < m \)), then a cycle is present. Otherwise, no cycle exists.

inputFormat

The input is read from standard input (stdin) with the following format:

Line 1: An integer n, the number of nodes in the linked list.
Line 2: n space-separated integers representing the node values.
Line 3: An integer k, indicating the index of the node that the last node links to. If k is -1, there is no loop.

Notes: The linked list is 0-indexed.

outputFormat

Output to standard output (stdout) a single line: True if the linked list contains a loop, and False otherwise.

4
1 2 3 4
-1

False