有序合并单链表

#include "stdafx.h"
#include <stdlib.h>

typedef int DATA_TYPE;

typedef struct _node
{
    DATA_TYPE data;
    struct _node *next;
}node_t;
typedef node_t *LINKLIST;

void show_list(LINKLIST head);

LINKLIST create_list(int size)
{
    int i = 0;
    LINKLIST head;
    node_t *p, *r;

    head = (node_t *)malloc(sizeof(node_t));
    p = r = head;
    printf("create an int list with size of %d:\n", size);
    while( ++i <= size )
    {
        p = (node_t *)malloc( sizeof(node_t) );
        p->data = rand()%1000;
        r->next = p;
        r = p;
        r->next = NULL;
    }

    return head;
}

LINKLIST merge_link(node_t *pa, node_t *pb)
{
    LINKLIST head;
    node_t *pr;

    head = (node_t *)malloc( sizeof(node_t) );
    head->next = NULL;
    pr = head;

    while(pa && pb)
    {
        if(pa->data <= pb->data)
        {
            pr->next = pa;
            pr = pa;
            pa = pa->next;
        }
        else
        {
            pr->next = pb;
            pr = pb;
            pb = pb->next;
        }
    }
    pr->next = pa ? pa : pb;

    return head->next;
}

node_t* mergeSort(node_t *alist)
{
    node_t *first;
    node_t *second;
    first = alist;
    second = alist->next;

    if(NULL == first || NULL == second)
    {
        return alist; //only one node left
    }
    //devide alist to 2 lists by middle
    while(second != NULL && second->next != NULL)
    {
        alist = alist->next;
        second = second->next->next;
    }
    second = alist->next;//(alist.len + 1)/2
    alist->next = NULL;

    return merge_link( mergeSort(first), mergeSort(second) );
}

void show_list(LINKLIST head)
{
    node_t *p = head;
    //p = head->next;
    while(p)
    {
        printf("%d", p->data);
        p = p->next;
        if(p) printf("->");
    }
    printf("\n");
}


int _tmain(int argc, _TCHAR* argv[])
{
    int n;
    node_t *plist;
    node_t *psort;

    printf("Please input the length of link:\n");
    scanf("%d", &n);
    plist = create_list( n );// with head
    show_list(plist->next); // without head

    psort = mergeSort(plist->next);// without head
    printf("after merge sort:\n");
    show_list(psort);

    return 0;
}

    “堆排序、快速排序这些在数组排序时性能非常好的算法，在链表只能“顺序访问”的限制下无法施展魔力；但是归并排序却如鱼得水，非但保持了它O(nlogn)的时间复杂度，而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。真是好得不得了啊，哈哈。”