题解 | #单链表的排序#

1. 注意快慢指针找中点。
2. 记住默认结尾是NULL，所以不需要给右端点。
3. 至于前面这一节的右端点，找出中点之后，mid->next = NULL即可。因为新数组会以一个新的head连接起来。所以head->next == NULL是返回条件

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here

        if(head == NULL || head->next == NULL){ //没有元素（防止异常的），或者只有一个元素
            return head;
        }

        // 快慢指针
        ListNode * slow = head; ListNode* fast = head->next;

        while( fast!=NULL&& fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode * right_1 = slow->next; //相当于新的head（有百年的）
        slow->next = NULL;
        ListNode * left_result = sortInList(head);
        ListNode * right_result = sortInList(right_1);


        ListNode * new_head = new ListNode(-1);
        ListNode * res = new_head;

        while(left_result!=NULL&&right_result!=NULL){

            if(left_result->val < right_result->val){
                new_head->next = left_result;
                left_result = left_result->next;
            }else{
                new_head->next  = right_result;
                right_result = right_result->next;
            }
            new_head = new_head->next;
        }

        if(left_result!=NULL){
            new_head->next = left_result;
        }else{
            new_head->next = right_result;
        }

        return res->next;

    }
};