New update is available. Click here to update.

Topics

Problem

Submissions

Solutions

Discuss

Cycle Detection in a Singly Linked List

Moderate

0/80

Average time to solve is 15m

Contributed by

99 upvotes

+113 more companies

Problem statement

You are given a Singly Linked List of integers. Return true if it has a cycle, else return false.

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

Example:

In the given linked list, there is a cycle, hence we return true.

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. Hence -1 would never be a list element.

The second line contains the integer position 'pos', representing the position (0-indexed) in the linked list where the tail connects. If 'pos' is -1, there is no cycle in the linked list.

Output format :

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

Note :

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

Sample Input 1 :

1 2 3 4 -1
1

Sample Output 1 :

true

Explanation of Sample Input 1:

The linked list given in the input is as follows:

Sample Input 2 :

1 2 3 4 -1
0

Sample Output 2 :

true

Explanation of Sample Input 2:

The linked list given in the input is as follows:

Sample Input 3 :

5 -1
-1

Sample Output 3 :

false

Explanation of Sample Input 3:

 The linked list given in the input is as follows:

Expected Time Complexity:

Try to solve this problem in O(n).

Expected Space Complexity:

Try to solve this problem in O(1).

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

Console