题解 | #单链表的排序#

链表的排序和普通的排序唯一的区别应该在于需要重新创建新的链表？因为创建新的链表在思路上比较简单~

我们还是先得到链表的长度，从而定义链表长度大小的数组，将链表中的val存储进数组，然后对于数组进行一个归并排序的处理，最后创建一个新的链表即可。

思路过于复杂了qaq，有看到的大佬可以分享一下更为简便的方法吗~awa

void merge(int arr[],int left,int mid,int right)
{
    int len1 = mid - left+1;//3
    int len2 = right - mid;//2//0 1 2 3 4
    int arr1[len1];
    int arr2[len2];
    for(int i=0;i<len1;i++)
    {
        arr1[i] = arr[left+i];
    }
    for(int i=0;i<len2;i++)
    {
        arr2[i] = arr[mid+1+i];
    }
    int out[right-left+1];
    int pos = 0;
    int pos1=0;
    int pos2=0;
    while(pos1<len1&&pos2<len2)
    {
        if(arr1[pos1]<arr2[pos2])
        {
            out[pos] = arr1[pos1];
            pos1++;
        }
        else if(arr1[pos1]>=arr2[pos2])
        {
            out[pos] = arr2[pos2];
            pos2++;
        }
        pos++;
    }
    while(pos1<len1)
    {
        out[pos] = arr1[pos1];
        pos1++;
        pos++;
    }
    while(pos2<len2)
    {
        out[pos] = arr2[pos2];
        pos2++;
        pos++;
    }
    for(int i=0;i<right-left+1;i++)
    {
        arr[left+i] = out[i];
    }
}
void mergesort(int arr[],int left,int right)
{
    if(left>=right)
    {
        return;
    }
    int mid = (left + right)/2;
    mergesort(arr, left, mid);
    mergesort(arr, mid+1,right);
    merge(arr,left,mid,right);
}
int getlen(struct ListNode* head)
{
    int cnt = 0;
    while(head!=NULL)
    {
        cnt++;
        head = head->next;
    }
    return cnt;
}
struct ListNode* createnode(int val)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(node!=NULL)
    {
        node->next = NULL;
        node->val = val;
        return node;
    }
    return NULL;
}
struct ListNode* sortInList(struct ListNode* head ) {
    // write code her
    int len = getlen(head);
    if(len==0)
    {
        return NULL;
    }
    int arr[len];
    for(int i=0;i<len;i++)
    {
        if(head!=NULL)
        {
            arr[i] = head->val;
            head =head ->next;
        }
        else 
        {
            printf("...some error\n");
        }
    }
    mergesort(arr,0,len-1);
    struct ListNode* newhead = createnode(arr[0]);
    struct ListNode* output = newhead;
    for(int i=1;i<len;i++)
    {
        struct ListNode* newnode = createnode(arr[i]);
        if(newnode!=NULL)
        {
            newhead->next = newnode;
            newhead = newhead->next;
        }
    }
    return output;
}