Detect The Cycle

Easy

0/40

Contributed by

48 upvotes

Asked in companies

Problem statement

Kevin has given you a Singly Linked List that contains only integers. You have to determine if it forms a cycle or not.

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

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

Input format :

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' that 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 :

The only line of output contains 'true' if the linked list has a cycle or 'false' otherwise.

You don't have to explicitly print by yourself. It has been taken care of.

Follow Up:

Try to solve this problem in O(N) Time Complexity and O(1) space Complexity.

Constraints :

0 <= N <= 10^6
-1 <= POS < N
-10^9 <= DATA <= 10^9 and DATA != -1

Where 'N' is the size of the singly linked list, 'POS' represents the position (0-indexed) in the linked list where the tail connects to and 'DATA' is the Integer data of the singly linked list.

Time Limit: 1 sec

Sample Input 1 :

3 2 0 -4 -1
1

Sample Output 1 :

true

Explanation of Sample Input 1:

The linked list has a cycle that connects back to index 1.

Sample Input 2 :

1 -1
-1

Sample Output 2 :

false

Hint 1

Think of 2 people starting from the initial node. One person takes a single jump and the other person takes twice the first person's jump each time. Extend this idea on every node and track the destination of both persons. Draw it on paper and find what happens!

Approaches (1)

Approach 1

Slow And Fast Pointer Approach

Time Complexity

Space Complexity

(100% EXP penalty)

Detect The Cycle

Console