Detect And Remove Cycle

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.

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.

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.

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.