题解 | #牛的品种排序IV#

这题的解法与NB12 牛群的身高排序一致，更详细的见上一题

/**
 * 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* sentry = new ListNode(-1);
            ListNode* excute = sentry;
            while(h1 != nullptr && h2 != nullptr){
                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 sentry->next;
        }
    }

    ListNode* sortCowsIV(ListNode* head) {
        // write code here
        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(sortCowsIV(head), sortCowsIV(midle));
    }
};