calgorithmdata-structureslinked-listfloyd-cycle-finding

How the loops are removed from link list

For instance if the link list is like :

1->2->3->4->5->6->7->8->9->4

We can find the loop using Floyd Cycle Algorithm but how to remove the loop in such cases?.

Solution 
  • 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.

    e.g. of your case: 1->2->3->4->5->6->7->8->9->4

    1) Loop verified by Floyd's cycle detection algo.
2) count of nodes in loop = 6
3) head->1, p->7 (6th node from head)
4) Loop while head!=p head=head->next and p=p->next. Both will meet at node 4
5) p=p->next Loop while(p->next!=head) p=p->next;
   Put p->next=NULL after termination of above loop. Your new list will be 1->2->3->4->5->6->7->8->9->NULL