题解 | #单链表的排序#

采用归并排序解决，注意在链表二分地方多加小心。

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */


struct ListNode* merge(struct ListNode* left_head,struct ListNode* right_head){
    struct ListNode* resul = (struct ListNode*)malloc(sizeof(struct ListNode));
    resul->next = NULL;
    struct ListNode* temp = resul;

    while(left_head!=NULL&&right_head!=NULL){
        if(left_head->val>right_head->val){
            temp->next = right_head;
            right_head = right_head->next;
        }else{
            temp->next = left_head;
            left_head = left_head->next;
        }
        temp = temp->next;
    }

    while(left_head!=NULL)
    {
        temp->next = left_head;
        left_head = left_head->next;
        temp = temp->next;
    }

    while(right_head!=NULL)
    {
        temp->next = right_head;
        right_head = right_head->next;
        temp = temp->next;
    }

    return resul->next;
}

struct ListNode* MergeSort(struct ListNode* head){
    //递归出口
    if(head==NULL || head->next==NULL){
        return head;
    }

    //fast速度是slow两倍，将链表二分
    struct ListNode* slow = head;
    struct ListNode* fast = head->next->next;
    struct ListNode* left = head;
    while(fast!=NULL && fast->next!=NULL){
        slow = slow->next;
        fast = fast ->next->next;
    }
    //右边链表的起始
    struct ListNode* right = slow->next;
    //两个链表分开独立
    slow->next = NULL;
    struct ListNode* left_resul = MergeSort(left);
    struct ListNode* right_resul = MergeSort(right);
    return merge(left_resul,right_resul);
}


struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode* p = head;
    return MergeSort(p);
}