单链表的归并排序

版权声明：本文为博主原创文章，转载请注明出处。 https://blog.csdn.net/twilight_karl/article/details/52972278

简单的归并排序的例子

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

typedef struct S
{
    int num;
    struct S * next ;
}LinkList;

void initList_p(LinkList * );
void initList_q (LinkList * q);
LinkList *  setList();
void show (LinkList * );
LinkList * Merge(LinkList * ,LinkList * );

int main (){
    LinkList * p = setList();
    LinkList * q = setList();
    initList_p (p);
    initList_q(q);
    printf("排序前的p:  ");
    show(p);
    putchar ('\n');
    printf("排序前的q:  ");
    show(q);
    LinkList * result  = Merge(p,q);
    printf("\n排序的结果:  ");
    show (result);
    putchar ('\n');
    system("pause");
    return 0;
}

void initList_p(LinkList * s)
{
    LinkList * m = s;
    for (int i = 1 ; i <= 10 ; i = i+2){
        LinkList * temp = (LinkList * )malloc (sizeof(LinkList ));
        temp ->next = NULL;
        temp ->num = i;
        m->next = temp ;
        m = m->next ;
    }
}
void initList_q (LinkList * q){
    LinkList * m = q;
    for (int i = 2 ; i <= 10 ; i= i+2){
        LinkList * temp = (LinkList * )malloc (sizeof(LinkList ));
        temp ->next = NULL;
        temp ->num = i;
        m->next = temp ;
        m = m->next ;
    }
}
LinkList *  setList(){
    LinkList * a = (LinkList * )malloc (sizeof (LinkList ));
    a->next = NULL;
    return a ;
}
void show (LinkList * p ){
    LinkList * temp = p ->next ;
    while (temp != NULL){
        printf ("%d ",temp ->num );
        temp = temp ->next ;
    }
}
LinkList * Merge (LinkList * a ,LinkList * b ){
    LinkList * p ,*q ,* pre ;
    p = a->next ;
    q = b->next ;
    pre = a;
    free(b);
    while(p != NULL && q != NULL){
        if (p->num  < q->num ){
            pre = p ;
            p = p ->next ;
        }else {
            b = q ;
            q = q->next ;

            pre ->next = b;
            b ->next = p;
            pre = pre ->next ;
        }
    }
    if(q != NULL){
        pre ->next = q;
    }
    return a;
}