fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class Node {
  6. public:
  7.     Node* next;
  8.     int id;
  9.     Node(int id, Node* next) : id(id), next(next) {}
  10.  
  11. };
  12.  
  13. Node* FindLoopBegin(Node *head) {
  14. 	if(!head) {
  15. 		return NULL;
  16. 	}
  17.     Node *slowptr = head,*fastptr = head;
  18.     do {
  19.         fastptr = fastptr->next;
  20.         if(fastptr == NULL) {return NULL;}
  21.         fastptr = fastptr->next;
  22.         slowptr = slowptr->next;
  23.     }while(slowptr && fastptr && slowptr != fastptr);
  24.     if(slowptr && fastptr && slowptr == fastptr) {
  25.         slowptr = head;
  26.         while(slowptr != fastptr){
  27.             slowptr = slowptr->next;
  28.             fastptr = fastptr->next;
  29.         }
  30.         return slowptr;
  31.     }   
  32.     return NULL;
  33. }
  34.  
  35. int main()
  36. {
  37.    Node* n10 = new Node(10,NULL);
  38.    Node* n12 = new Node(12,NULL);
  39.    Node* n14 = new Node(14,NULL);
  40.    n12->next = n14;
  41.    n14->next = n12;
  42.    n10->next = n12;
  43.    cout<<(FindLoopBegin(n10)->id)<<endl;
  44.    return 0;
  45. }
Success #stdin #stdout 0s 3228KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12
https://ideone.com/Qn5Krh
language:
C++14 (gcc 8.3)
created:
10 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!