题解 | #单链表的排序#

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next==nullptr) return head;
        ListNode* slow,*fast,*pre;
        pre = head;
        slow = head->next;
        fast = head->next->next;
        while(fast!=nullptr && fast->next!=nullptr) {
            pre = pre->next;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* sortedHead = sortInList(head);
        ListNode* sortedSlow = sortInList(slow);
        return merge(sortedHead, sortedSlow);
    }
    ListNode* merge(ListNode* p,ListNode* q){
        if(p==nullptr) return q;
        if(q==nullptr) return p;
        if(p->val < q->val){
            p->next = merge(p->next, q);
            return p;
        }
        else{
            q->next = merge(p, q->next);
            return q;
        }
    }
};