题解 | #单链表的排序#

方法1 开辟新数组

• 空间复杂度：O(n) ---开辟了一个大小为n的数组储存元素
• 时间复杂度：O(nlogn) ---对数组里的元素进行排序
• 根据排序好的数组新建链表

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

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr) return head;
        vector<int> s;
        while(head){
            s.push_back(head->val);
            head = head->next;
        }
        sort(s.begin(), s.end());
        ListNode* cur = new ListNode(-1);
        head = cur;
        for(int i = 0; i < s.size(); i++){
            ListNode* node = new ListNode(s[i]);
            cur->next = node;
            cur = cur->next;
        }
        return head->next;
        
    }
};

方法二 归并排序

用快慢指针找到中间节点一分为二，然后归并（相当于树的后序遍历），归并操作为将两条链表合并为一条有序链表

• 空间复杂度：O(1) ---原地排序
• 时间复杂度：O(nlogn) ---归并的复杂度

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next ==nullptr) return head;
        //fast开始时位于2，slow位于1，这样当fast走到空时，slow：奇数个节点找到中点，偶数个节点找到中心左边的节点。
        ListNode* fast = head->next;
        ListNode* slow = head; 
        while(fast != nullptr && fast->next != nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = nullptr;
        //归并排序：相当于树的后序遍历，先处理两边，再处理中间（左右中）
        ListNode* left =  sortInList(head);
        ListNode* right = sortInList(tmp);
        //将两条链表升序排序
        ListNode* h = new ListNode(-1);
        ListNode* cur = h;
        while(left && right){
            if(left->val < right->val){
                cur->next = left;
                left = left->next;
            }else{
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        if(left) cur->next = left;
        if(right) cur->next = right;
        return h->next;
    }
};