描述

给定一个节点数为n的无序单链表，按升序排序
输入：
[1,3,2,4,5]
返回值：
{1,2,3,4,5}
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

解题思路

方法一：辅助数组sort排序

用vector容器创建一个数组res，遍历链表并将链表中的数据存进res中，将res数组中的数据排序好之后再重新放回链表的对应结点中

class Solution {
public:
    
    ListNode* sortInList(ListNode* head) {
        int i=0;
        vector<int>res;
        ListNode* p = head;
        ListNode* p1 = head;
        if(p==nullptr) return NULL;
        while(p){
            res.push_back(p->val);
            p=p->next;
        }
        sort(res.begin(),res.end());
        while(p1){
            p1->val = res[i++];
            p1=p1->next;
        }
        return head;
    }
};

时间复杂度：O(NlogN)，N链表的长度，遍历链表，排序复杂度NlogN；
空间复杂度：O(N)，链表存储与读取数据

方法二：归并排序

先利用快慢指针找出链表的中点，然后分为两个链表，一直分，直到无法分为止，然后自底而上排序归并
在这里插入图片描述

class Solution {
public:
    
    ListNode* sortInList(ListNode* head) {
        if(head==nullptr||head->next==nullptr) return head;
        //归并排序
        ListNode* mid = middleNode(head);
        ListNode* left = sortInList(head);
        ListNode* right = sortInList(mid);
        return merge(left,right);
    }
    //使用双指针将链表分成两段
    ListNode* middleNode(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next!=nullptr && fast->next->next!=nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* cur = slow->next;
        slow->next = nullptr;
        return cur;
    }
    ListNode* merge(ListNode* head1,ListNode* head2){
        ListNode* dummyHead = new ListNode(0);
        ListNode* pre = dummyHead;
        while(head1!=nullptr&&head2!=nullptr){
            if(head1->val<head2->val){
                pre->next=head1;
                pre=head1;
                head1=head1->next;
            }else{
                pre->next=head2;
                pre=head2;
                head2=head2->next;
            }
        }
        pre->next = head1==nullptr ? head2:head1;
        return dummyHead->next;
        
    }
};