Linked List Cycle II

Moderate

0/80

Average time to solve is 10m

Contributed by

158 upvotes

Asked in companies

Problem statement

You are given a singly linked list that may or may not contain a cycle. You are supposed to return the node where the cycle begins, if a cycle exists, else return 'NULL'.

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

1 2 3 4 -1
1

Sample Output 1 :

Explanation For Sample Input 1 :

For the first test case,

Sample Input 2 :

1 2 3 4 -1
0

Sample Output 2 :

Explanation For Sample Input 2 :

For the first test case,

Follow-Up:

Can you do this in O(n) time and using constant space?

Constraints :

-10^4 <= n <= 10^4
-1 <= pos < n
-10^9 <= data <= 10^9 and data != -1

Time Limit: 1 sec

Console