fork download
copy 
  1. #include <stdio.h>
  2.  
  3. typedef struct node {
  4.     int val;
  5.     struct node* next;
  6.                }node;
  7.  
  8. struct node* create_node(int val) {
  9.     struct node* new_node = (struct node*)malloc(sizeof(struct node));
  10.     new_node->val = val;
  11.     new_node->next = NULL;
  12.     return new_node;
  13. }
  14.  
  15.    void insert_tail(struct node** head_ref, int val) {
  16.     struct node* new_node = create_node(val);
  17.     if (*head_ref == NULL) {
  18.         *head_ref = new_node;
  19.         return;
  20.     }
  21.     struct node* temp = *head_ref;
  22.     while (temp->next)
  23.         temp = temp->next;
  24.     temp->next = new_node;
  25.                            }
  26.  
  27.      node *find_mid(node *head){
  28.       if(!head) return head;
  29.       node *slow,*fast;
  30.       fast = slow = head;
  31.       node *prev=NULL;
  32.       while(fast && fast->next){
  33.          prev=slow;
  34.          fast=fast->next->next;
  35.          slow=slow->next;
  36.       }
  37.       if(prev) prev->next=NULL;
  38.       return slow;   
  39.      } 
  40.  
  41.      node *merge_sorted(node *n1,node *n2){
  42.       if(!n1) return n2;
  43.       if(!n2) return n1;
  44.       node *head = NULL;
  45.       if(n1->val<n2->val){
  46.          head=n1;
  47.          head->next=merge_sorted(n1->next,n2);}
  48.       else {
  49.          head = n2;
  50.          head->next = merge_sorted(n1,n2->next);
  51.      }
  52.      return head;}
  53.  
  54.      node* Merge_sort(node *head){
  55.       if(!head || !head->next) return head;
  56.       node *mid = find_mid(head);
  57.       node *left = Merge_sort(head);
  58.       node *right = Merge_sort(mid);
  59.       head = merge_sorted(left,right);
  60.       return head;
  61.      }
  62.  
  63.     int main() {
  64.       node *head=NULL;
  65.       for(int i=5;i>=0;--i) insert_tail(&head,i);
  66.       head = Merge_sort(head);
  67.       node *temp=head;
  68.       while(temp){
  69.          printf("%d ",temp->val);
  70.          temp=temp->next;
  71.       }
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 1 2 3 4 5
https://ideone.com/sgi8gc
language:
C (gcc 8.3)
created:
3 days 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!