fork(1) download 
  1.  
  2. #include<iostream>
  3. using namespace std;
  4. class node{
  5. public:
  6.     int data;
  7.     node *next;
  8.     node(int d){
  9.     data = d;
  10.     next = NULL;
  11.     }
  12. };
  13.  
  14. void insertAtTail(node *&head, int data){
  15.     if(head==NULL){
  16.         head= new node(data);
  17.         return;
  18.     }
  19.     node *tail = head;
  20.     while(tail->next!=NULL){
  21.         tail=tail->next;
  22.     }
  23.     tail->next=new node(data);
  24.     return;
  25. }
  26. void buildInput(node *&head){
  27.     int data;
  28.     cin>>data;
  29.     while(data!=-1){
  30.         insertAtTail(head,data);
  31.         cin>>data;
  32.     }
  33. }
  34.  
  35. //racer technique
  36. node *midPoint(node *head){
  37.     if(head==NULL || head->next==NULL){
  38.         return head;
  39.     }
  40.     node *slow =head;
  41.     node *fast = head->next;
  42.     while (fast!=NULL && fast->next!=NULL){
  43.  
  44.         fast=fast->next->next;
  45.          slow=slow->next;
  46.     }
  47.     return slow;
  48. }
  49.  
  50. node *Merge(node *a, node *b){
  51.     //base case
  52.     if(a==NULL){
  53.         return b;
  54.     }
  55.     else if (b==NULL){
  56.         return a;
  57.     }
  58.     //compare a and b
  59.     node *c;
  60.     if(a->data < b->data){
  61.         c=a;
  62.         c->next = Merge(a->next,b);
  63.     }
  64.     else{
  65.         c=b;
  66.         c->next = Merge(a,b->next);
  67.     }
  68.     return c;
  69.  
  70. }
  71. node *mergeSort(node *head){
  72.     //base case
  73.     if(head==NULL || head->next==NULL){
  74.         return head;
  75.     }
  76.     //rec case
  77.     //1.divide
  78.     node *mid = midPoint(head);
  79.     node *a = head;
  80.     node *b = mid->next;
  81.     mid->next = NULL;
  82.     //2.recursive sort
  83.     a = mergeSort(a);
  84.     b = mergeSort(b);
  85.     //3.merge  a and b
  86.     node *c = Merge(a,b);
  87.     return c;
  88.  
  89. }
  90. void print(node *head){
  91.     //node *temp=head;
  92.     while(head!=NULL){
  93.         cout<<head->data;
  94.         head=head->next;
  95.     }
  96. }
  97. int main(){
  98.     node *head=NULL;
  99.     buildInput(head);
  100.     /*node *m= midPoint(head);
  101.     cout<<m->data;*/
  102.     //print(head);
  103.     mergeSort(head);
  104.     print(head);
  105. return 0;}
  106.  
Time limit exceeded #stdin #stdout 5s 5888KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HUeucO
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!