Last Updated: 28 Jan, 2021

Moderate

Problem statement

A cycle occurs when a node's next pointer returns to a previous node in the list.

Example:
``````In the given linked list, there is a cycle starting at position 0, hence we return 0.
``````

Input Format :
``````The first line contains the elements of the singly linked list separated by a single space and terminated by -1; 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.
``````

Note:
``````You are not required to print the expected output; it has already been handled. Just implement the function.
``````

Approaches

01 Approach

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.