fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class Node
  5. {
  6. public:
  7.     int data;
  8.     Node *next;
  9.     Node(int d)
  10.     {
  11.         data = d;
  12.         next = NULL;
  13.     }
  14. };
  15.  
  16. // head - Head pointer of the Linked List
  17. // Return a boolean value indicating the presence of cycle
  18. // If the cycle is present, modify the linked list to remove the cycle as well
  19. bool floydCycleRemoval(Node *head)
  20. {
  21.  
  22.     Node *slow=head;
  23.     Node *fast=head;
  24.  
  25.     //update for the case  5 -1 is the i/p
  26.     if(fast == NULL or fast->next == NULL) return false;
  27.     while(fast!=NULL || fast->next!=NULL){
  28.         fast=fast->next->next;
  29.         slow=slow->next;
  30.         // update a long i/p   with no cycle
  31.         if(fast == NULL or fast->next == NULL) return false;
  32.         if(slow==fast){
  33.            Node* temp = fast;
  34.            slow = head;
  35.            while(temp->next!=slow->next){
  36.             temp=temp->next;
  37.             slow=slow->next;
  38.         }
  39.         temp->next=NULL;
  40.            return true;
  41.         }
  42.  
  43.  
  44.     }
  45.     return false;
  46. }
  47.  
  48. void buildCycleList(Node *&head)
  49. {
  50.     unordered_map<int, Node *> hash;
  51.     int x;
  52.     cin >> x;
  53.     if (x == -1)
  54.     {
  55.         head = NULL;
  56.         return;
  57.     }
  58.     head = new Node(x);
  59.     hash[x] = head;
  60.     Node *current = head;
  61.     while (x != -1)
  62.     {
  63.         cin >> x;
  64.         if (x == -1)
  65.             break;
  66.         if (hash.find(x) != hash.end())
  67.         {
  68.             current->next = hash[x];
  69.             return;
  70.         }
  71.         Node *n = new Node(x);
  72.         current->next = n;
  73.         current = n;
  74.         hash[x] = n;
  75.     }
  76.     current->next = NULL;
  77. }
  78.  
  79. void printLinkedList(Node *head)
  80. {
  81.     unordered_set<int> s;
  82.     while (head != NULL)
  83.     {
  84.         if (s.find(head->data) != s.end())
  85.         {
  86.             cout << "\nCycle detected at " << head->data;
  87.             return;
  88.         }
  89.         cout << head->data << " ";
  90.         s.insert(head->data);
  91.         head = head->next;
  92.     }
  93. }
  94.  
  95. int main()
  96. {
  97.     Node *head = NULL;
  98.  
  99.     buildCycleList(head);
  100.  
  101.     bool cyclePresent = floydCycleRemoval(head);
  102.     if (cyclePresent)
  103.     {
  104.         cout << "Cycle was present\n";
  105.     }
  106.     else
  107.     {
  108.         cout << "No cycle\n";
  109.     }
  110.  
  111.     cout << "Linked List - ";
  112.     printLinkedList(head);
  113.  
  114.     return 0;
  115. }
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
1 -> 2 -> 3
stdout
copy 
Cycle was present
Linked List - 1 0
https://ideone.com/oDztaD
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

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!