题解 | #单链表的排序#

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* getMid(ListNode* head) {
        if(!head) {
            return head;
        }
        ListNode* fast = head, *slow = head;
        ListNode* prev = slow;
        while(fast && fast->next) {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr;
        return slow;
    }
    
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(!pHead1) {
            return pHead2;
        }
        if (!pHead2) {
            return pHead1;
        }
        ListNode *head = new ListNode(0);
        ListNode *ret = head;
        while(pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                head->next = new ListNode(pHead1->val);
                pHead1 = pHead1->next;
            } else {
                head->next = new ListNode(pHead2->val);
                pHead2 = pHead2->next;
            }
           head = head ->next;
        }
        if (pHead1) {
            head->next = pHead1;
        }
        if (pHead2) {
            head->next = pHead2;
        }
        return ret->next;
    }
    
    ListNode* sortInList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* mid = getMid(head);
        ListNode *left = sortInList(head);
        ListNode *right = sortInList(mid);
        return Merge(left, right);        
        // write code here
    }
};