New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Cycle Detection in a Singly Linked List

Contributed by

Arindam Majumder

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 15 mins

Success Rate 80 %

52 upvotes

Problem Statement

You have given a Singly Linked List of integers, determine if it forms a cycle or not.

A cycle occurs when a node's next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.

Note: Since, it is binary problem, there is no partial marking. Marks will only be awarded if you get all the test cases correct.

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" which represents the position (0-indexed) in the linked list where 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 linked list has a cycle or 'false' otherwise.

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

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 tail connects to and "data" is the Integer data of singly linked list.

Time Limit: 1 sec

Note :

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

Sample Input 1 :

3 2 0 -4 -1
1

Sample Output 1 :

true

Sample Input 2 :

1 -1
-1

Sample Output 2 :

false

Sample Input 3 :

1 2 -1
1

Sample Output 3 :

true

Auto

Console