题解 | #单链表的排序# C语言：归并排序

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */

//归并算法
void MergeSort(int* a,int left,int right,int* tmp)
{
    if(left>=right)
    {
        return;
    }

    int mid =(left+right)>>1;   //相当于除以2
    MergeSort(a,left,mid,tmp);
    MergeSort(a,mid+1,right,tmp);
    int begin1=left,end1=mid;
    int begin2=mid+1,end2=right;
    int index=left;

    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1]<a[begin2])
        {
            tmp[index++]=a[begin1++];
        }
        else 
        {
            tmp[index++]=a[begin2++];
        }
    }
    while(begin1<=end1)
    {
        tmp[index++]=a[begin1++];
    }
    while(begin2<=end2)
    {
        tmp[index++]=a[begin2++];
    }
    //将tmp拷贝到a[]中
    for(int i=left;i<=right;i++)
    {
        a[i]=tmp[i];
    }
}

struct ListNode* sortInList(struct ListNode* head ) 
{
    int size=0;
    struct ListNode* cur=head;
    while(cur != NULL)
    {
        size++;
        cur=cur->next;
    }
    //将链表中的元素复制到数组中
    int* a=(int*)malloc(sizeof(int)*size);
    cur=head;
    for(int i=0;cur != NULL;i++)
    {
        a[i]=cur->val;
        cur=cur->next;
    }
    int* tmp=(int*)malloc(sizeof(int)*size);
    MergeSort(a,0,size-1,tmp);
    //将a中的值拷贝到head中
    cur=head;
    for(int i=0;cur != NULL;i++)
    {
        cur->val=a[i];
        cur=cur->next;
    }
    free(tmp);
    free(a);

    return head;
}