题解 | #牛群的身高排序#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    
    // 常规的链表合并
    ListNode* MyMerge(ListNode* h1, ListNode* h2){
        if(h1 == nullptr){
            return h2;
        }else if (h2 == nullptr) {
            return h1;
        }else {
            ListNode* NewHead = new ListNode(0);
            ListNode* excute = NewHead;
            while (h1 && h2) {
                if(h1->val > h2->val){ // 因为升序，要小的
                    excute->next = h2;
                    h2 = h2->next;
                }else {
                    excute->next = h1;
                    h1 = h1->next;
                }
                excute = excute->next;
            }
            if(h1 != nullptr){
                excute->next = h1;
            }else {
                excute->next = h2;
            }
            return NewHead->next;
        }
    }

    ListNode* sortList(ListNode* head) {
        // 解题思路：利用分治思想，先分片后合并
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        ListNode* left = head;
        ListNode* midle = head->next;
        ListNode* right = head->next->next;
        // 分治操作，利用一步两步的快慢指针操作来找中来分片
        while(right != nullptr && right->next != nullptr){
            left = left->next;  // 慢指针的前一个
            midle = midle->next; // 慢指针（一步）
            right = right->next->next;  // 快指针（两步）
        }
        left->next = nullptr;  // 打断操作
        return MyMerge(sortList(midle), sortList(head));
    }
};