fork download
copy 
  1. // C++ program to detect and remove loop 
  2. #include <bits/stdc++.h> 
  3. using namespace std; 
  4.  
  5. struct Node { 
  6. 	int key; 
  7. 	struct Node* next; 
  8. }; 
  9.  
  10. Node* newNode(int key) 
  11. { 
  12. 	Node* temp = new Node; 
  13. 	temp->key = key; 
  14. 	temp->next = NULL; 
  15. 	return temp; 
  16. } 
  17.  
  18. // A utility function to print a linked list 
  19. void printList(Node* head) 
  20. { 
  21. 	while (head != NULL) { 
  22. 		cout << head->key << " "; 
  23. 		head = head->next; 
  24. 	} 
  25. 	cout << endl; 
  26. } 
  27.  
  28. // Function to detect and remove loop 
  29. // in a linked list that may contain loop 
  30. void detectAndRemoveLoop(Node* head) 
  31. { 
  32. 	// If list is empty or has only one node 
  33. 	// without loop 
  34. 	if (head == NULL || head->next == NULL) 
  35. 		return; 
  36.  
  37. 	Node *slow = head, *fast = head; 
  38.  
  39. 	// Move slow and fast 1 and 2 steps 
  40. 	// ahead respectively. 
  41. 	slow = slow->next; 
  42. 	fast = fast->next->next; 
  43.  
  44. 	// Search for loop using slow and 
  45. 	// fast pointers 
  46. 	while (fast && fast->next) { 
  47. 		if (slow == fast) 
  48. 			break; 
  49. 		slow = slow->next; 
  50. 		fast = fast->next->next; 
  51. 	} 
  52.  
  53. 	/* If loop exists */
  54. 	if (slow == fast) { 
  55. 		slow = head; 
  56. 		while (slow->next != fast->next) { 
  57. 			slow = slow->next; 
  58. 			fast = fast->next; 
  59. 		} 
  60.  
  61. 		/* since fast->next is the looping point */
  62. 		fast->next = NULL; /* remove loop */
  63. 	} 
  64. } 
  65.  
  66. /* Driver program to test above function*/
  67. int main() 
  68. { 
  69. 	Node* head = newNode(50); 
  70. 	head->next = head; 
  71. 	head->next = newNode(20); 
  72. 	head->next->next = newNode(15); 
  73. 	head->next->next->next = newNode(4); 
  74. 	head->next->next->next->next = newNode(10); 
  75.  
  76. 	/* Create a loop for testing */
  77. 	head->next->next->next->next->next = head->next->next; 
  78.  
  79. 	detectAndRemoveLoop(head); 
  80.  
  81. 	printf("Linked List after removing loop \n"); 
  82. 	printList(head); 
  83.  
  84. 	return 0; 
  85. } 
  86.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Linked List after removing loop 
50 20 15 4 10
https://ideone.com/A1BEjB
language:
C++14 (gcc 8.3)
created:
6 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!