题解 | #单链表的排序#

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

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

void Sort(int *arr, int left, int mid, int right)
{
    int tmp[right-left+1];
    int l = left;
    int m = mid + 1;
    int i = 0;
    int j = 0;

    while(l <= mid && m <= right)
    {
        if (arr[l] > arr[m])
        {
            tmp[i++] = arr[m++];
        }
        else 
        {
            tmp[i++] = arr[l++];
        }        
    }
    while(l <= mid)
    {
        tmp[i++] = arr[l++];
    }
    while(m <= right)
    {
        tmp[i++] = arr[m++];
    }
    for (i = 0, j = left; j <=right; i++, j++)
    {
        arr[j] = tmp[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);
    Sort(arr, left, mid, right);
}

struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode* phead = head;
    int arr[100000] = {0};
    int i = 0;
    for (i = 0; phead != NULL; i++, phead = phead->next)
    {
        arr[i] = phead->val;
    }
    MergeSort(arr, 0, i-1);
    

    phead = head;
    for (i = 0; phead != NULL; i++, phead = phead->next)
    {
        phead->val = arr[i];
    }
    return head;
}