struct ListNode* mid(struct ListNode* head);//中点分割函数
struct ListNode* merge(struct ListNode* head1,struct ListNode* head2);//排序合并两个链表
struct ListNode* sortInList(struct ListNode* head){
    if(head == NULL || head->next == NULL)
        return head;
    //递归终止条件 最终只剩下一个节点的时候返回
    struct ListNode* head1 = head;
    struct ListNode* head2 = mid(head);
    //printf("%d %d\n",head1->val,head2->val);
    head1 = sortInList(head1);
    head2 = sortInList(head2);
 

    return merge(head1,head2);
}
 

struct ListNode* mid(struct ListNode* head)
{
  //快慢指针找中点，返回第二段链表的头节点
    struct ListNode* H=malloc(sizeof(struct ListNode));
    H->next=head;
    struct ListNode* slow = H;
    struct ListNode* fast = H;
 
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
 
    struct ListNode* temp = slow->next;
    slow->next = NULL;
 
    return temp;
}
 
struct ListNode* merge(struct ListNode* head1,struct ListNode* head2)
{
  //排序合并两个链表
    struct ListNode* H =(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur = H;
    while(head1 != NULL && head2 != NULL)
    {
        if(head1->val < head2->val)
        {
            cur->next = head1;
            head1 = head1->next;
        }
        else
        {
            cur->next = head2;
            head2 = head2->next;
        }
        cur = cur->next;
    }
    if(head1!=NULL)
        cur->next=head1;
    if(head2!=NULL)
        cur->next=head2;
    return H->next;
}

int cmp(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    int num[1000000];
    int i=0;
    while(head!=NULL)
    {
        num[i++]=head->val;//存入链表的val值
        head=head->next;
    }
    qsort(num, i, sizeof(int), cmp);//快排
    struct ListNode* H=malloc(sizeof(struct ListNode));
    struct ListNode* cur=H;
    int j=0;
  //创建新链表
    while(j!=i)
    {
        struct ListNode* temp=malloc(sizeof(struct ListNode));
        temp->next=NULL;
        temp->val=num[j++];
        cur->next=temp;
        cur=temp;
    }
    return H->next;
}