Problem

Submissions

Hints & solutions

Discuss

Cycle Detection in a Singly Linked List

Moderate

0/80

Average time to solve is 15m

Contributed by

178 upvotes

Asked in 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

Hint 1

Hint 2

Hint 3

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

Approaches (3)

Approach 1

Approach 2

Approach 3

Outer And Inner Loop

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 head.
If the inner-loop visits the node next to the outer-loop node, then return true, else repeat the process for the next iteration of outer-loop.
If outer-loop reaches the end of list or null, then return false.

Time Complexity

O(N*N), where N is the total number of nodes.

For every iteration of outer-loop, we are iterating the linked-list again.

Space Complexity

O(1).

Constant space is used.

(75% EXP penalty)

(100% EXP penalty)

Cycle Detection in a Singly Linked List

Console