题解 | #单链表的排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
#设置一个辅助数组拷贝出链表中的值，用归并排序来进行排序后又拷贝回链表中
#include<stdlib.h>
void merge(int *arr,int lo, int mid, int hi);
void mergeSort(int *arr,int lo, int hi)
{
    if(lo == hi) return;
    int mid = (lo +hi) >> 1;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo ,mid, hi);
}
void merge(int *arr,int lo, int mid, int hi)
{
    int *B = (int*)malloc((mid -lo + 1)*sizeof(int));
    int i = 0, j = 0, k = 0;
    for(j = lo; j <= mid; j++)
    {
        *(B + (i ++)) = *(arr + j);
    }
    for(i = 0, k = lo, j = mid +1; i <= mid -lo;)
    {
        *(arr + (k++)) = *(B + i) < *(arr + j) || j > hi ? *(B + (i ++)) : *(arr + (j++));
    }
    free(B);
}
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    int *arr = (int*)malloc(100000*sizeof(int));
    int i = 0, len = 0;
    struct ListNode *p = head;
    while(p)
    {
        *(arr + (i ++)) = p->val;
        p = p->next;
    }
    len = i;
    mergeSort(arr,  0, len - 1);
    p = head;
    i = 0;
    while(p)
    {
        p->val = *(arr + (i ++));
        p = p->next;
    }
    free(arr);
    return head;
}