蔡子经数据结构3.5

#include <stdlib.h>
#include <time.h>
#define MAXN 100

typedef struct 
{
    int val;
    struct * next;
} node;

node *createNode()
{
    node *ret = (node*)malloc(sizeof(node));
    ret->val = 0;
    ret->next = NULL;
    return ret;
}

node *createList(int n)
{
    srand(time(0));
    node *head = createNode();
    for(int i = 0; i < n; ++i)
    {
        node *p = createNode();
        p->val = rand()%100;
        p->next = head->next;
        head->next = p;
    }
    return head;
}

node* mergeSort(node *p)
{
    if(p == NULL) return p;
    if(p->next == NULL) return p;//如果只有一个节点，直接返回
    node *fst = p;
    node *sed = p->next;
    while(sed->next)//快慢指针来寻找链表的中间位置
    {
        fst = fst->next;
        sed = sed->next;
        if(sed->next == NULL) break;
        sed = sed->next;
//        if(sed->next == NULL) break;
    }
    sed = fst->next;
    fst->next = NULL;
    fst = p;
    fst = mergeSort(fst);
    sed = mergeSort(sed);
    p = NULL;
    node *ret = NULL;
    while(fst && sed)
    {
        if(fst->val < sed->val)
        {
            if(p == NULL)
                ret = p = fst;
            else
            {
                p->next = fst;
                p = p->next;
            }
            fst = fst->next;
        }
        else
        {
            if(p == NULL)
                ret = p = sed;
            else
            {
                p->next = sed;
                p = p->next;
            }
            sed = sed->next;
        }
    }
    while(fst)
    {
        p->next = fst;
        fst = fst->next;
    }
    while(sed)
    {
        p->next = sed;
        sed = sed->next;
    }
    return ret;
}

int main()
{
    int n = 10;
    node *head = createList(n);
    node *p = head->next;
    while(p)
    {
        printf("%dn",p->val);
        p = p->next;
    }
    p = head->next;
    free(head);
    head = mergeSort(p);//返回一个没有头结点的指针
    puts("----------------------------");
    while(head)
    {
        printf("%dn",head->val);
        head = head->next;
    }
    return 0;
}