148. 排序链表

原题链接:148. 排序链表

solution:

        ①先遍历链表,保存每一个节点。O(n)
        ②sort根据每个节点值进行排序。O(nlog(n))
        ③根据新的顺序创建链表。        O(n)

总的时间复杂度：nlog(n)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector L;
        while(head != nullptr) {
            L.push_back(head);
            head = head->next;
        }
        sort(L.begin(),L.end(),[](ListNode *a,ListNode *b){
            return a->val < b->val;
        });
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        for(auto &x : L) {
            cur->next = new ListNode(x->val);
            cur = cur->next;
        }
        return dummy->next;
    }
};

归并的思想：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;

        ListNode *slow = head;
        ListNode *fast = head;  //定义快慢指针,慢指针最后抵达链表中点
        while(fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // slow指向中间节点，现在需要把前后段分开
        fast = slow;
        slow = slow->next;
        fast->next = nullptr;

        ListNode *left = sortList(head);
        ListNode *right = sortList(slow);

        return mergeTwoLists(left,right);
    }


      ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1);
        ListNode *cur = dummy;
        while(list1 != nullptr && list2 != nullptr){
            if(list1->val <= list2->val){
                cur->next = list1;
                list1 = list1->next;
                cur = cur->next;
            }
            else{
                cur->next = list2;
                list2 = list2->next;
                cur = cur->next;
            }
        }
        if(list1 != nullptr) cur->next = list1;
        else cur->next = list2;
        
        return dummy->next;
    }
};