题解 | #单链表的排序#NC70，CCCCCC

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    if(head==NULL) return head;
    int n,i=0;
    struct ListNode *L;
    L=head;
    printf("%d",head->val);
    for(i=1;L!=NULL;i++){                                   //找节点个数，n-1个
        L=L->next;
    }
    L=head;                                                 //L换回头节点，方便下次
    n=i;
    int *array;                                        //数组存val值
    array=NULL;
    array=(int *)malloc(sizeof(int)*n);
    for(i=1;i<n;i++){                              //存入
        array[i]=L->val;
        L=L->next;
    }
    int low,high,mid;                              //nlogn 时间复杂度，用二分法
    for(i=2;i<n;i++){
        array[0]=array[i];
        low=1;
        high=i-1;
        while(low<=high){                           
            mid=(low+high)/2;
            if(array[mid]>=array[0]){                      
               high=mid-1;
            }
            else{
                low=mid+1;
            }
        }                                     //跳出的时候，array[i]=array[0]放在high+1位置
        int j=0;
        for(j=i-1;j>high;j--){                //把high+1至i-1后移一位，，high+1也要移动
            array[j+1]=array[j];
        }
        array[high+1]=array[0];   
    }
    L=head;                             //L换回头节点，next和数组下标i,结合数据放进原链表。不用申请新的链表
    for(i=1;i<n&&L!=NULL;i++){
            L->val=array[i];
            L=L->next;
        }
    return head;
}