fork(2) download
copy 
  1. // Detect_Remove_Loop_LList.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include <stdio.h>
  5. #include <iostream>
  6. #include <stdlib.h>
  7. using namespace std;
  8.  
  9. class Node{
  10. int data;
  11. public:
  12.         Node *pNext;
  13.         Node():data(0),pNext(NULL){};
  14.         Node(int n){
  15.                 data = n;
  16.         }
  17. };
  18. bool FindAndRemoveLoopInList(Node **nodesList)
  19. {
  20.         //make sure nodeslist is not null or single valued
  21.         if(*nodesList == NULL || (*nodesList)->pNext == NULL)
  22.                 return false;
  23.  
  24.         bool bResult = false;
  25.         Node *slowNode = *nodesList , *fastNode = (*nodesList); Node *prevSlowNode = NULL;
  26.         while(slowNode != NULL && fastNode != NULL){    //This condition will become false if there is no loop in list
  27.  
  28.     			if(fastNode->pNext ==NULL)
  29.                         break;
  30. 				//Slownode advances by one and fastnode advances by two
  31. 				//Save prevSlowNode to make use of it in remove loop case
  32. 				prevSlowNode = slowNode;
  33.                 slowNode = slowNode->pNext;
  34.                 fastNode = fastNode->pNext->pNext;
  35.  
  36.                 if(slowNode == fastNode)
  37.                 {
  38.                         bResult = true;
  39.                         break;
  40.                 }
  41.  
  42.         }
  43.  
  44. 		//To remove loop in the list
  45. 		if(bResult)
  46. 		{
  47. 			/*Move fastNode to start node and move both nodes at same pace now.
  48. 			They will meet at head node of loop.*/
  49. 			fastNode = *nodesList;
  50. 			while(fastNode != slowNode)
  51. 			{
  52. 				prevSlowNode = slowNode;
  53. 				slowNode = slowNode->pNext;
  54. 				fastNode = fastNode->pNext;
  55. 			}
  56. 			//Loop head is at slownode position now.Make its prev node to null.
  57. 			prevSlowNode->pNext = NULL;
  58. 		}
  59.         return bResult;
  60. }
  61.  
  62.  void CleanupList(Node *llist)
  63.  {
  64. 	while(llist != NULL)
  65. 	{
  66. 		Node *tempNode = llist;
  67. 		llist = llist->pNext;
  68. 		delete tempNode;
  69. 	}
  70.  }
  71.  
  72. int main(int argc, char* argv[])
  73. {
  74.         Node *nodes=NULL;
  75.  
  76. 		//Create some list with 10 nodes
  77.         for(int i=0;i<10;i++)
  78.         {
  79.                 int n = i+rand()%50;
  80.                 Node *node = new Node(n);
  81.                 node->pNext = NULL;
  82.                 if(nodes == NULL)
  83.                         nodes = node;
  84.                 else
  85.                 {
  86.                         node->pNext=nodes;
  87.                         nodes= node;
  88.                 }
  89.         }
  90.         //Lets make a loop to the last element to second element
  91.         Node *tmpNode = NULL;
  92.         for(tmpNode = nodes;tmpNode->pNext != NULL;tmpNode=tmpNode->pNext);
  93.         tmpNode->pNext = nodes->pNext;
  94.  
  95.         bool bResult = FindAndRemoveLoopInList(&nodes);
  96. 		if(bResult)
  97. 			cout<<"Loop has been detected and removed!!"<<endl;
  98. 		else
  99. 			cout<<"No loop found"<<endl;
  100.  
  101. 		//Cleanup allocated memory
  102. 		CleanupList(nodes);
  103.         return 0;
  104. }
  105.  
  106.  
Success #stdin #stdout 0s 2984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Loop has been detected and removed!!
https://ideone.com/Hl2xat
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!