Linked List Cycle Detection

Given a singly linked list, determine whether the list contains a cycle. A cycle occurs when a node's next pointer points to a previous node in the list. This problem can be solved using Floyd's Tortoise and Hare algorithm, which uses two pointers moving at different speeds. If there is a cycle, the two pointers will eventually meet; otherwise, the fast pointer will reach the end of the list.

The time complexity of this approach is \(O(n)\) and the space complexity is \(O(1)\), where \(n\) is the number of nodes in the linked list.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n) representing 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) which indicates the index (0-indexed) of the node that the last node's next pointer should point to, creating a cycle. If (pos = -1), then there is no cycle.

outputFormat

Output a single line to standard output (stdout) containing either "True" if the linked list contains a cycle, or "False" otherwise.## sample

4
3 2 0 -4
1

True