Cycle Detection in a Singly Linked List

Given a singly linked list, determine whether it contains a cycle. A cycle in a linked list occurs if one of the nodes can be reached again by continuously following the next pointer. The most efficient solution is to use Floyd's Tortoise and Hare algorithm, where a slow pointer moves one step at a time and a fast pointer moves two steps at a time. If there is a cycle, the two pointers will eventually meet. The algorithm can be summarized as follows: $$ slow = head, \ fast = head.next $$ and then repeatedly updating until they meet or reach the end of the list.

inputFormat

The input begins with an integer n representing the number of nodes in the linked list. The second line contains n integers separated by a space that denote the node values (if n > 0, otherwise this line will be empty). The third line contains an integer pos which indicates the index (0-indexed) to which the tail node is connected to create a cycle. If pos is -1, then there is no cycle in the linked list.

outputFormat

Output a single line containing "True" if the linked list contains a cycle, or "False" otherwise.

4
1 2 3 4
-1

False