New update is available. Click here to update.

Problem

Submissions

Solution

New

Discuss

Detect And Remove Cycle

Contributed by

Sakshi Bansal

Last Updated: 23 Feb, 2023

Easy

0/40

Avg time to solve 10 mins

Success Rate 90 %

33 upvotes

Problem Statement

Suggest Edit

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.

In the 2nd test case, there is no cycle.

Sample Input 2 :

Sample Output 2 :

True
1 1 1 -1
False
3 -3 -1

Auto

Console

LinkedLists Notes

Reverse List in K groups

Sum Between Zeroes

Rearrange Linked List

Clone Linked List with Random Pointer

Merge Two Sorted Linked Lists

Detect and Remove Cycle

Remove String

Add First and Second Half

Intersection of Linked List

Left Short

Count Inversion

Flatten The Multi-Level Linked List

Count triplets in a sorted doubly linked list whose sum is equal to a given value x

Deletion in Circular Linked List