Detect and Remove Loop in a Linked List

如何detect环？

环上追击问题，两个速度不相等的pointer 一定相遇。

Method 1 (Check one by one) 

We know that Floyd’s Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the above diagram). We store the address of this in a pointer variable say ptr2. Then we start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. When we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get pointer to the previous of this node.
环上的任意一点设为ptr2，从head开始用一个ptr1指着，每次move to head.next。Loop这个环如果什么时候ptr2.next == ptr1，说明这是第一个从头上看和环交叉的点，是环的起点。

  if (slow == fast)   
     removeLoop(slow, node);  
   // Function to remove loop  
   void removeLoop(Node loop, Node curr) {  
     Node ptr1 = null, ptr2 = null;  
     /* Set a pointer to the beging of the Linked List and  
      move it one by one to find the first node which is  
      part of the Linked List */  
     ptr1 = curr;  
     while (1 == 1) {  
       /* Now start a pointer from loop_node and check if it ever  
        reaches ptr2 */  
       ptr2 = loop;  
       while (ptr2.next != loop && ptr2.next != ptr1) {  
         ptr2 = ptr2.next;  
       }  
       /* If ptr2 reahced ptr1 then there is a loop. So break the  
        loop */  
       if (ptr2.next == ptr1) {  
         break;  
       }  
       /* If ptr2 did't reach ptr1 then try the next node after ptr1 */  
       ptr1 = ptr1.next;  
     }  
     /* After the end of loop ptr2 is the last node of the loop. So  
      make next of ptr2 as NULL */  
     ptr2.next = null;  
   }  

Method 2 (Better Solution)
This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

Method 3 (Optimized Method 2: Without Counting Nodes in Loop)
We do not need to count number of nodes in Loop. After detecting the loop, if we start slow pointer from head and move both slow and fast pointers at same speed until fast don’t meet, they would meet at the beginning of linked list.

How does this work?
Let slow and fast meet at some point after Floyd’s Cycle finding algorithm. Below diagram shows the situation when cycle is found.

We can conclude below from above diagram

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

(m + n*x + k) = 2*(m + n*y + k)

Note that before meeting the point shown above, fast
was moving at twice speed.

x -->  Number of complete cyclic rounds made by 
       fast pointer before they meet first time

y -->  Number of complete cyclic rounds made by 
       slow pointer before they meet first time

From above equation, we can conclude below

    m + k = (x-2y)*n

Which means m+k is a multiple of n. 

So if we start moving both pointers again at same speed such that one pointer (say slow) begins from head node of linked list and other pointer (say fast) begins from meeting point. When slow pointer reaches beginning of linked list (has made m steps). Fast pointer would have made also moved m steps as they are now moving same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning. Can they meet before also? No because slow pointer enters the cycle first time after m steps.