New update is available. Click here to update.

Detect And Remove Cycle

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.

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.

Approach 1

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.

Try Problem

Approach 2

In this approach, we will use a hash table to store the visited nodes. We will traverse the list, and for each node, if it is not present in the hash table we will add it, else if the node is already there is the hash table, it means there is a cycle. Assume this node as ‘cur’, to remove the cycle we have to find the previous node of the ‘cur’ node and change its ‘next’ values to NULL.

Try Problem

Approach 3

Finding the cycle

The idea is to have 2 pointers: slow and fast. Slow pointer takes a single jump and corresponding to every jump slow pointer takes, fast pointer takes 2 jumps. If there exists a cycle, both slow and fast pointers will reach the exact same node. If there is no cycle in the given linked list, then the fast pointer will reach the end of the linked list well before the slow pointer reaches the end or NULL.

Why slow and fast meet at a node?

After some moves, there will be a situation where both fast and slow pointers are in the cycle.

After each move, the distance between pointer fast and slow decreases by 1. So after 2 moves (2 is the initial distance between fast and slow pointer), both pointers will meet a node.

Initialize slow and fast at the beginning.
Start moving slow to every next node and move fast 2 jumps, while making sure that fast and its next is not null.
If slow and fast refer to the same node anytime during the process, there is a cycle, otherwise, repeat the process.
If fast reaches the end or NULL, then the execution stops and we can conclude that no cycle exists.

Removing the cycle

Find the length of the cycle, let’s say ‘L’.
We will take two pointers ‘ptr1’ and ‘ptr2’, initially ‘ptr1’ points to head and ‘ptr2’ points to Lth node from the head.
We will move the pointers until they meet at the same node.
To remove the cycle we have to find the previous node of the ‘ptr2’ and change its ‘next’ values to NULL.

Try Problem

Approach 4

We can find the cycle as we did in approach 2

Removing the cycle

Note: ‘start’ denotes the node where the cycle starts, ‘converge’ denotes the node where slow and fast pointers meet.

We have to find ‘start’.

Change slow such that it points to head.
Fast points to ‘converge’ node.
Move both fast and slow by 1 node until they meet at a node.
This node will be the ‘start’

To remove the cycle we have to find the previous node of ‘start’ and change its ‘next’ value to NULL.

This works because the distance of head node from ‘start’ is equal to the distance of ‘converge’ node from start.

Explanation

Let ‘k’ denote the length of the cycle.

We will prove a=b.

Distance travelled by fast pointer = 2 * (Distance travelled by slow pointer)

a + x*k + (k-b) = 2*( a + y*k + (k-b) )

Where x is complete cyclic rounds made by fast pointer and y is complete cyclic rounds made by slow pointer before they meet

=> x*k = a + 2*y*k + k - b

=> a - b = (x - 2*y - 1)*k

When we move in the cycle, the actual distance (displacement) we cover from the ‘start’ node is D%k ( where ‘D’ is the total distance we moved in the cycle )

(x - 2*y - 1)*k is a multiple,

=> (x-2*y-1)*k % k=0

Hence, we can say a=b.

Try Problem

Detect And Remove Cycle

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.

Input Format :

Output Format :

Note :

Constraints :

Approach 1

Approach 2

Approach 3

Approach 4

Interested in Coding Ninjas Flagship Courses?