fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. /* Link list node */
  5. struct node
  6. {
  7.     int data;
  8.     struct node* next;
  9. };
  10.  
  11. /* Function to remove loop. */
  12.  
  13.  
  14. /* This function detects and removes loop in the list
  15.   If loop was there in the list then it returns 1,
  16.   otherwise returns 0 */
  17. int detectAndRemoveLoop(struct node *head)
  18. {
  19.    struct node *slow = head;
  20.    struct node *fast = head;
  21.    while(slow!=NULL && fast!=NULL && fast->next!=NULL)
  22.    {
  23.    	if(slow==fast)
  24.    	{
  25.    	  removeLoop(slow,&head);
  26.    	  return 1;	
  27.    	}
  28.    }
  29.    return 0;
  30. }
  31. void removeLoop(struct node* slow,struct node** head)
  32. {
  33. 	struct node* last = *head;
  34. 	while(last->next!=slow)
  35. 	{
  36. 		last = last->next;
  37. 	}
  38. 	last->next = NULL;
  39. 	return;
  40. }
  41.  
  42. /* Function to remove loop.
  43.  loop_node --> Pointer to one of the loop nodes
  44.  head -->  Pointer to the start node of the linked list */
  45.  
  46.  
  47. /* UTILITY FUNCTIONS */
  48. /* Given a reference (pointer to pointer) to the head
  49.   of a list and an int, pushes a new node on the front
  50.   of the list. */
  51. void push(struct node** head_ref, int new_data)
  52. {
  53.     /* allocate node */
  54.     struct node* new_node =
  55.         (struct node*) malloc(sizeof(struct node));
  56.  
  57.     /* put in the data  */
  58.     new_node->data  = new_data;
  59.  
  60.     /* link the old list off the new node */
  61.     new_node->next = (*head_ref);
  62.  
  63.     /* move the head to point to the new node */
  64.     (*head_ref)    = new_node;
  65. }
  66.  
  67. /* Function to print linked list */
  68. void printList(struct node *node)
  69. {
  70.     while(node != NULL)
  71.     {
  72.         printf("%d  ", node->data);
  73.         node = node->next;
  74.     }
  75. }
  76.  
  77. /* Drier program to test above function*/
  78. int main()
  79. {
  80.     /* Start with the empty list */
  81.     struct node* head = NULL;
  82.  
  83.     push(&head, 10);
  84.     push(&head, 4);
  85.     push(&head, 15);
  86.     push(&head, 20);
  87.     push(&head, 50);
  88.  
  89.     /* Create a loop for testing */
  90.     head->next->next->next->next->next = head->next->next;
  91.  
  92.     detectAndRemoveLoop(head);
  93.  
  94.     printf("Linked List after removing loop \n");
  95.     printList(head);
  96.  
  97.     getchar();
  98.     return 0;
  99. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int detectAndRemoveLoop(node*)’:
prog.cpp:25:28: error: ‘removeLoop’ was not declared in this scope
       removeLoop(slow,&head);
                            ^
stdout
copy 
Standard output is empty
https://ideone.com/fTBpUo
language:
C++ (gcc 8.3)
created:
9 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!