题解 | #单链表的排序#

方法一：归并排序

1、利用归并排序将链表分而治之，不断地将链表从中间结点拆解为两个链表；

2、拆解至单个结点后进行排序，将问题转化为两个排序好的链表融合为一个链表的问题；自下而上递归将两个链表进行融合，最终得到排序后的链表。

利用快慢指针得到链表的中间结点

时间复杂度：o(nlog2​n)，每级划分最坏需要遍历链表全部元素，因此为o(n)，每级合并都是将同级的子问题链表遍历合并，因此也为o(n)，分治划分为二叉树型，一共有o(log2​n)层，因此复杂度为o((n+n)∗log2​n)=o(nlog2​n)。

空间复杂度：o(log2​n)，递归栈的深度最坏为树型递归的深度，log2​n层。

class Solution {
public:
    ListNode* merge(ListNode* phead1, ListNode* phead2) {
        if(phead1 == nullptr)
            return phead2;
        if(phead2 == nullptr)
            return phead1;
            
        ListNode* res = new ListNode(0);
        ListNode* newhead = res;

        while (phead1 && phead2) {
            if(phead1->val < phead2->val) {
                newhead->next = phead1;
                phead1 = phead1->next;
            } else {
                newhead->next = phead2;
                phead2 = phead2->next;
            }
            newhead = newhead->next;
        }
        
        if(phead1)
            newhead->next = phead1;
        if(phead2)
            newhead->next = phead2;

        return res->next;
    }

    ListNode* sortInList(ListNode* head) {
        //特殊情况处理
        if(head == nullptr || head->next == nullptr) 
            return head;
        //利用快慢指针得到链表的中间结点，将链表表从中点处拆分为两个链表
        ListNode* left = head;
        ListNode* middle = head->next;
        ListNode* right = head->next->next;
        while (right != nullptr && right->next != nullptr) {
            left = left->next;
            middle = middle->next;
            right = right->next->next;
        }
	  	//将左边链表拆分成独立的链表
        left->next = nullptr;
        //递归融合得到排序后的链表
        return merge(sortInList(head), sortInList(middle));
    }
};

方法二：将链表转换为数组排序求解

1、将链表转换为数组；

2、数组排序

3、将排序后的数组转换为链表。

时间复杂度：o(nlog2​n)，sort函数一般为优化后的快速排序，复杂度为o(nlog2​n)

空间复杂度：o(n)

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        //特殊情况处理
        if (head == nullptr || head->next == nullptr)
            return head;
		//链表转换为数组
        vector<int> vet;
        while (head) {
            vet.push_back(head->val);
            head = head->next;
        }
	  	//数组排序
        sort(vet.begin(), vet.end());
        ListNode* res = new ListNode(0);
        ListNode* newhead = res;
		//排序后的数组转换为链表
        for (int i = 0; i < vet.size(); i++) {
            newhead->next = new ListNode(vet[i]);
            newhead = newhead->next;
        }
        newhead->next = nullptr;
        return res->next;
    }
};