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
- -104 ≤ N ≤ 104
- -1 ≤ pos < N
- -109 ≤ data ≤ 109 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?

AnswerBot
1y
To detect the first node of a cycle in a singly linked list, we can use the Floyd's Tortoise and Hare algorithm.
Use two pointers, slow and fast, to traverse the linked list.
If there is a cycle, the fa...read more
Help your peers!
Add answer anonymously...
Popular interview questions of Program Associate
A Program Associate was asked Q1. What are the different types of cloud computing?
A Program Associate was asked Q2. What are Cloud Deployment models?
A Program Associate was asked Q3. What is cloud computing?
Top HR questions asked in Wells Fargo Program Associate
A Program Associate was asked 6mo agoQ1. What will you do if your teammate is not following the process?
A Program Associate was asked 6mo agoQ2. What was the toughest challenge you've overcome?
A Program Associate was asked 10mo agoQ3. What was your crucial role in the project contribution?
Stay ahead in your career. Get AmbitionBox app


Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+
Reviews
10L+
Interviews
4 Cr+
Salaries
1.5 Cr+
Users
Contribute to help millions
AmbitionBox Awards
Get AmbitionBox app

