Detect And Remove Cycle

Easy
0/40
Average time to solve is 10m
profile
Contributed by
41 upvotes
Asked in companies
WalmartOracleGoldman Sachs

Problem statement

You have been given a Singly Linked List of integers, determine if it forms a cycle or not. If there is a cycle, remove the cycle and return the list.

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

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

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 the tail connects to. If "pos" is -1, then there is no cycle in the linked list.
Output Format : 
For each test case, print two lines.

The first line contains 'True' if the linked list has a cycle, otherwise 'False'.

The second line 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.
Note : 
You don't have to explicitly print anything yourself. It has been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 5 * 10^4
-1 <= pos < N
-10^9 <= data <= 10^9 and data != -1

Where 'N' is the size of the singly linked list, and "data" is the Integer data of the singly linked list.
Sample Input 1 :
2
3 2 0 -4 -1
1
1 2 -1
-1
Sample Output 1 :
True
3 2 0 -4 -1
False
1 2 -1
Explanation for Sample Input 1 :
In the 1st test case, there is a cycle, from index 1 -> 2 -> 3 -> 1. The cycle's length is 3.

sample input1

In the 2nd test case, there is no cycle.
Sample Input 2 :
2
1 1 1 -1
0
3 -3 -1
-1
Sample Output 2 :
True
1 1 1 -1
False
3 -3 -1
Hint

Think of checking every node to detect the cycle.

Approaches (4)
Brute Force Approach

The basic idea is that for every node we will check if there is any node to its left that is creating a cycle.

 

Algorithm

 

  • If the head is NULL or the next of the head is NULL, return false.
  • Take two pointers ‘cur’(initialized to next node of head) and ‘prev’(initialized to head)
  • Initialize a variable ‘i’ with 1.
  • Run a loop while ‘cur’ is not NULL.
    • Update ‘prev’ to head.
    • Run a loop from 0 to i - 1 using a variable ‘j’.
      • If next of ‘cur’ is equals to ‘prev’ i.e.if there is a loop from ‘cur’ node to ‘prev’, return true;
      • Update ‘prev’ to next of ‘prev’.
    • Update ‘cur’ to next of ‘cur’.
    • Increment ‘i’.
  • If no cycle found, return false.
Time Complexity

O(N^2), Where ‘N’ is the number of nodes in the linked list.

 

For every node, we are checking all the nodes to their left. In the worst case, the time complexity will be O(N^2).

Space Complexity

O(1)


 

Constant space is used.

Code Solution
(100% EXP penalty)
Detect And Remove Cycle
Full screen
Console