题解 | #单链表的排序#

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

#include <cstddef>
class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    
    //得到中间的Node
    ListNode* middleLIst(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != nullptr && fast->next->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;

    }

    //合并两个链表  传进来的链表一定是有序的
    ListNode* mergeList(ListNode* lhs,ListNode* rhs)
    {
        if(lhs == nullptr) return rhs;
        if(rhs == nullptr) return lhs;
        ListNode* virhead = new ListNode(-1);
        ListNode *p = virhead;
        while(lhs != nullptr && rhs != nullptr)
        {
            if(lhs->val>rhs->val)
            {
                p->next = rhs;
                rhs = rhs->next;
            }
            else 
            {
                p->next = lhs;
                lhs = lhs->next;                
            }
            p = p->next;
        }
        if(rhs != nullptr) p->next = rhs;
        if(lhs != nullptr) p->next = lhs;
        p = virhead->next;
        delete virhead;
        return p;
    }

    ListNode* sortInList(ListNode* head) {
        // write code here
        //采用冒泡 超时
        // ListNode* virhead = new ListNode(-1);
        // virhead->next = head;
        // ListNode* p = virhead->next;
        // int len = 0;
        // bool flag = false;
        // while(p != nullptr)
        // {
        //     ++len,p = p->next;
        // }
        // for(int i = 0; i != len-1;++i)
        // {
        //     p = virhead;
        //     flag = true;
        //     for(int j = 0; j != len-i-1;++j)
        //     {
        //         if(p->next->val > p->next->next->val)
        //         {
        //             flag = false;
        //             ListNode* q = p->next;
        //             p->next = p->next->next;
        //             q->next = p->next->next;
        //             p->next->next = q;
        //         }
        //         p = p->next;
        //     }
        //     if(flag) break;
        // }
        // p = virhead->next;
        // delete virhead;
        // return p;

        // 采用归并
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* mid = middleLIst(head);
        ListNode* lhs = head;
        ListNode* rhs = mid->next;
        mid->next = nullptr;

        ListNode* lres = sortInList(lhs);
        ListNode* rres = sortInList(rhs);

        return mergeList(lres,rres);
    }
};