Detect the First Node of the Loop in a Singly Linked List

You are provided with a singly linked list that may contain a cycle. Your task is to return the node where the cycle begins, if such a cycle exists.

A cycle occurs if a node's next pointer points back to any preceding node in the list. This means the linked list will not have a distinct start and end but will cycle through a set of nodes.

Input:

The first line contains an integer ‘T’ that signifies the number of test cases. Each test case includes: The first line containing singly linked list elements, separated by a single space and ending with -1. Note that -1 is a terminator and not a list element. The second line includes an integer "pos" that indicates the 0-indexed position in the list where the tail connects back to form a cycle. If "pos" is -1, the linked list has no cycle.

Output:

For each test case, print the integer "pos" which indicates the 0-indexed position of the first node in the linked list that forms the cycle's start. Print -1 if there is no cycle in the linked list.

Example:

Input:
3
1 2 3 4 5 -1
-1
1 2 3 4 5 6 7 8 -1
2
1 -1
0
Output:
-1
2
0

Constraints:

• 0 ≤ T ≤ 50
• -10⁴ ≤ N ≤ 10⁴
• -1 ≤ pos < N
• -10⁹ ≤ data ≤ 10⁹ and data ≠ -1
• Time Limit: 1 sec

Note:

Simply implement the function; output handling is predefined.

Follow-Up:

Can you solve this problem using O(N) time complexity and constant space?