Detect Cycle in a Linked List

A linked list is a fundamental data structure where each node contains a value and a pointer to the next node. Sometimes, due to erroneous pointer assignments, the linked list can form a cycle. Your task is to determine whether a given linked list contains a cycle.

A cycle occurs if there exists a node in the list that can be reached again by continuously following the next pointer. One common technique to solve this problem is Floyd's Tortoise and Hare algorithm, which uses two pointers moving at different speeds.

For each test case, you will be given a sequence of node values and a position indicating where the tail of the list should be connected. If the position is -1, then no cycle exists. Otherwise, the tail node will link to the node at the specified position (0-indexed), forming a cycle.

inputFormat

The input contains multiple test cases. The first line contains an integer T, the number of test cases. For each test case:

1. The first line contains an integer n (n >= 0), the number of nodes in the linked list.
2. The second line contains n space-separated integers representing the node values. If n is 0, the line will be empty.
3. The third line contains an integer pos, representing the 0-indexed position where the tail should be connected. A value of -1 means no cycle should be created.

outputFormat

For each test case, output a single line containing 'True' if the linked list contains a cycle, or 'False' otherwise.## sample

1
4
3 2 0 -4
1

True