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