Linked List Cycle II

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
163 upvotes
Asked in companies
GoogleVisaAdobe

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.

Sample Example 1

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 :
1


Explanation For Sample Input 1 :
For the first test case,

Sample Input 1

Sample Input 2 :
1 2 3 4 -1
0


Sample Output 2 :
0


Explanation For Sample Input 2 :
For the first test case,

Sample Input 2

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
Hint

Think of checking each node as the starting point for the cycle.

Approaches (3)
Outer And Inner Loop

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.
Time Complexity

O(N ^ 2), where ‘N’ is the total number of nodes.

 

For every iteration of the outer loop, we are iterating the linked list again. So the overall time complexity will be O(N^2).

Space Complexity

O(1)

 

We are using constant extra space. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Linked List Cycle II
Full screen
Console