Detecting a Cycle in a Linked List

You are given a singly linked list. Your task is to detect if the linked list contains a cycle. A cycle occurs when a node's next pointer points to one of the previous nodes in the list.

The cycle detection must be implemented using the Floyd’s Tortoise and Hare algorithm. In other words, if we denote the positions in the linked list by indices, then once a fast pointer that moves two steps at a time and a slow pointer that moves one step at a time meet, a cycle exists. This can be formally expressed as: \(\exists\, t:\ slow(t)=fast(t)\) if a cycle exists.

The linked list is provided via standard input. You need to construct the linked list according to the input format, detect whether there is a cycle and print True if a cycle exists, otherwise print False.

inputFormat

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

n
v1 v2 v3 ... vn
pos

Here, the first line is an integer n representing the number of nodes in the linked list. The second line contains n space-separated integers representing the values of the nodes. The third line contains an integer pos which indicates the 0-indexed position that the last node’s next pointer should point to. If pos is -1, it means that there is no cycle.

outputFormat

The output is a single line printed to standard output (stdout) containing either True if the linked list contains a cycle or False otherwise.

5
1 2 3 4 5
1

True