'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Linked List Cycle II

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

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 )
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
Full screen
Console