sysprog21_w2_qa from louielu

ll.c

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

typedef struct list {
    int data;
    struct list *next;
} LIST;


LIST *append( LIST *, int );
LIST *sort( LIST * );
LIST *list_switch( LIST *, LIST * );
void print_list( LIST * );

void print_list( LIST *t )
{
    while( t != NULL ) {
        printf( "%d, ", t->data );
        t = t->next;
    }
    printf("\n");
}

LIST *append( LIST *start, int newdata )
{
    LIST *new, *end, *ret;

    if( (new = (LIST *)malloc(sizeof(LIST))) == NULL) {
        fprintf( stderr, "Memory Allocation error.\n" );
        // In Windows, replace following with a return statement.
        exit(1);
    }
    if( start == NULL )
        ret = new;
    else {
        ret = start;
        end = start;
        while( end->next != NULL ) end = end->next;
        end->next = new;
    }
    new->data = newdata;
    new->next = NULL;
    return ret ;
}

LIST *sort( LIST *start )
{
    if( start == NULL ) return NULL;
    /* First push the larger items down */
    if( start->next !=NULL && start->data > start->next->data )
        start = list_switch( start, start->next );
    /* Always sort from second item on */
    start->next = sort(start->next);
    /* bubble smaller items up */
    if( start->next !=NULL && start->data > start->next->data ) {
        start = list_switch( start, start->next );
        start->next = sort(start->next);
    }
    return start;
}

LIST *get_middle(LIST *start)
{
    LIST *head = start;
    LIST *tail = start;

    for (; tail->next != NULL && tail->next->next != NULL; ) {
        head = head->next;
        tail = tail->next->next;
    }

    return head;
}

LIST *merge(LIST *left, LIST *right)
{
    LIST *dummy = NULL, *cur;

    dummy = append(dummy, 0);
    cur = dummy;

    while (left != NULL && right != NULL) {
        if (left->data > right->data) {
            cur->next = right;
            right = right->next;
        } else {
            cur->next = left;
            left = left->next;
        }
        cur = cur->next;
    }

    cur->next = (left != NULL) ? left : right;

    return dummy->next;
}

LIST *merge_sort(LIST *start)
{
    LIST *middle, *half;
    if (start == NULL || start->next == NULL)
        return  start;

    middle = get_middle(start);
    half = middle->next;
    middle->next = NULL;

    return merge(merge_sort(start), merge_sort(half));
}

LIST *list_switch( LIST *l1, LIST *l2 )
{
    l1->next = l2->next;
    l2->next = l1;
    return l2;
}

int main(void)
{
    LIST *try;
    int i;

    // This is just testing code
    try = NULL;
    try = append( try, 5 );
    try = append( try, 2 );
    try = append( try, 9 );
    try = append( try, 8 );
    try = append( try, 1 );
    try = append( try, 7 );
    try = append( try, 3 );

    printf("Original list:\n");
    print_list( try );
    try = merge_sort( try );
    printf("Sorted list:\n");
    print_list( try );
    return 0;
}