#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// your basic linked list node
struct node
{
    int data;
    struct node *next;
};

void print_list(struct node *list)
{
    while (list)
    {
        printf("%d ", list->data);
        list = list->next;
    }
    printf("\n");
}
//////////////////////////////////////////////////////////////////////


// merge two sorted linked lists.
struct node *merge(struct node *list1, struct node *list2)
{
    struct node *res = NULL;
    struct node **pp = &res;
    
    // while we have two lists
    while (list1 && list2)
    {
        if (list1->data <= list2->data)
        {
            *pp = list1;
            list1 = list1->next;
        }
        else
        {   // second was larger
            *pp = list2;
            list2 = list2->next;
        }
        pp = &(*pp)->next;
    }

    // link unfinished list to last node.
    *pp = (list1 ? list1 : list2);
    return res;
}
//////////////////////////////////////////////////////////////////////


// merge-sort a linked list. uses the two pointer method to
//  walk the linked list and find the mid-point.
struct node *merge_sort(struct node* list)
{
    struct node *p1 = list;
    struct node **pp = &list;
    
    if (!(list && list->next))
        return list;
    
    while (p1 && p1->next)
    {
        p1 = p1->next->next;
        pp = &(*pp)->next;
    }

    // p1 will start the "right" side, *pp terminates the "left" side.
    p1 = *pp;
    *pp = NULL;
    
    // now "merge" the merge_sort()s of the two sides
    return merge(merge_sort(list), merge_sort(p1));
}
//////////////////////////////////////////////////////////////////////


int main()
{
    struct node *list = NULL;
    struct node **pp = &list;
    int i = 0;
    
    srand((unsigned)time(NULL));
    
    for (i=0; i<25; ++i)
    {
        *pp = malloc(sizeof(**pp));
        (*pp)->data = rand() % 100;
        pp = &(*pp)->next;
    }
    *pp = NULL;
    
    print_list(list);
    list = merge_sort(list);
    print_list(list);
    return 0;
}