fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. // your basic linked list node
  6. struct node
  7. {
  8.     int data;
  9.     struct node *next;
  10. };
  11.  
  12. void print_list(struct node *list)
  13. {
  14.     while (list)
  15.     {
  16.         printf("%d ", list->data);
  17.         list = list->next;
  18.     }
  19.     printf("\n");
  20. }
  21. //////////////////////////////////////////////////////////////////////
  22.  
  23.  
  24. // merge two sorted linked lists.
  25. struct node *merge(struct node *list1, struct node *list2)
  26. {
  27.     struct node *res = NULL;
  28.     struct node **pp = &res;
  29.  
  30.     // while we have two lists
  31.     while (list1 && list2)
  32.     {
  33.         if (list1->data <= list2->data)
  34.         {
  35.             *pp = list1;
  36.             list1 = list1->next;
  37.         }
  38.         else
  39.         {   // second was larger
  40.             *pp = list2;
  41.             list2 = list2->next;
  42.         }
  43.         pp = &(*pp)->next;
  44.     }
  45.  
  46.     // link unfinished list to last node.
  47.     *pp = (list1 ? list1 : list2);
  48.     return res;
  49. }
  50. //////////////////////////////////////////////////////////////////////
  51.  
  52.  
  53. // merge-sort a linked list. uses the two pointer method to
  54. //  walk the linked list and find the mid-point.
  55. struct node *merge_sort(struct node* list)
  56. {
  57.     struct node *p1 = list;
  58.     struct node **pp = &list;
  59.  
  60.     if (!(list && list->next))
  61.         return list;
  62.  
  63.     while (p1 && p1->next)
  64.     {
  65.         p1 = p1->next->next;
  66.         pp = &(*pp)->next;
  67.     }
  68.  
  69.     // p1 will start the "right" side, *pp terminates the "left" side.
  70.     p1 = *pp;
  71.     *pp = NULL;
  72.  
  73.     // now "merge" the merge_sort()s of the two sides
  74.     return merge(merge_sort(list), merge_sort(p1));
  75. }
  76. //////////////////////////////////////////////////////////////////////
  77.  
  78.  
  79. int main()
  80. {
  81.     struct node *list = NULL;
  82.     struct node **pp = &list;
  83.     int i = 0;
  84.  
  85.     srand((unsigned)time(NULL));
  86.  
  87.     for (i=0; i<25; ++i)
  88.     {
  89.         *pp = malloc(sizeof(**pp));
  90.         (*pp)->data = rand() % 100;
  91.         pp = &(*pp)->next;
  92.     }
  93.     *pp = NULL;
  94.  
  95.     print_list(list);
  96.     list = merge_sort(list);
  97.     print_list(list);
  98.     return 0;
  99. }
Success #stdin #stdout 0s 2380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
76 3 44 22 78 50 42 68 48 82 17 10 81 46 43 38 5 62 4 18 98 95 0 33 14 
0 3 4 5 10 14 17 18 22 33 38 42 43 44 46 48 50 62 68 76 78 81 82 95 98
https://ideone.com/GHmT1j
Linked List MergeSort Implementation
language:
C (gcc 8.3)
created:
12 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!