Detect the first node of the loop

Posted: 28 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given a singly linked list which may or may not contain a cycle. You are supposed to return the node where the cycle begins (if a cycle exists).

A cycle occurs when a node's next pointer points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains the elements of the singly linked list separated by a single space and terminated by -1 and hence -1 would never be a list element.

The second line contains the integer position "pos" which represents the position (0-indexed) in the linked list where the tail connects to. If "pos" is -1, then there is no cycle in the linked list.
Output Format :
For each test case, print the integer position “pos” which represents the position of (0-indexed) in the linked list which is the first node of the cycle. Print -1 if there is no cycle in the linked list.

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
0 <= T <= 50
-10^4 <= N <= 10^4
-1 <= pos < N
-10^9 <= data <= 10^9 and data != -1

Time Limit: 1 sec
Follow Up:
Can you do this in O(N) time and usingconstant space?
Approach 1

The basic idea of this approach is to check each node as the starting point for the cycle. 

Now consider the following steps:

  • We are going to have two loops outer-loop and inner-loop.
  • Maintain a count of the number of nodes visited in outer-loop.
  • For every node of the outer-loop, start the inner loop from the head.
    • If the inner-loop visits the node next to the outer-loop node, then we have found the starting point of the cycle which is the current node of inner-loop, otherwise repeat the process for the next iteration of outer-loop.
  • If outer-loop reaches the end of list or null, then cycle doesn’t exist in the given linked list.
Try Problem