leetcode_效率题解_148. Sort List_（链表归并排序）

相关题解：
leetcode_效率题解_[python/C++]_147. Insertion Sort List（链表插入排序）

题目链接
【题目】
Sort a linked list in O(n log n) time using constant space complexity.

【分析】
O(nlogn)的复杂度我们很显然想到归并排序，快速排序

记得大一的时候写链表排序的题都是先转成数组或者vector然后再进行排序，贴出来以便大家熟悉一下数组的归并排序

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if( head == NULL ) return head;
        vector<int> vec;
        while( head != NULL ){
            vec.push_back(head->val);
            head = head->next;
        }
        int size = vec.size();
        merge_sort( vec , 0 , size - 1 );
        ListNode * List = new ListNode(vec[0]);
        ListNode * ans = List;
        for( int i = 1 ; i < size ; i ++ ){
            ListNode * temp = new ListNode(vec[i]);
            ans->next = temp;
            ans = ans->next;
        }
        return List;

    }
    void merge( vector<int>& a , int low , int mid , int high ){
        vector<int> temp( high - low + 1 , 0 );
        int i = low , j = mid+1 , m = mid , n = high , k = 0;
        while( i <= m && j <= n ){
            if( a[i] < a[j] ) temp[k++] = a[i++];
            else temp[k++] = a[j++];
        }
        while( i <= m ) temp[k++] = a[i++];
        while( j <= n ) temp[k++] = a[j++];
        for( int g = 0 ; g < k ; g ++ ) a[low+g] = temp[g];
    }
    void merge_sort( vector<int>& a , int low , int high ){
        if( low < high ){
            int mid = ( low + high )/2;
            merge_sort( a , low , mid );
            merge_sort( a , mid+1 , high );
            merge( a , low , mid , high );
        }
    }
};

然而效率是这样的

所以归根到底我们还是得用指针来写：
那重点在哪里呢，在于如何找到一个链表的mid
这里我用了下面一段代码来找到分界点second_head

ListNode * slow = head;
        ListNode * fast = head->next;
        while(fast&&fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode * second_head = slow->next;
        slow->next = NULL;

所以就简单了：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if( !head || !head->next ) return head;
        ListNode * slow = head;
        ListNode * fast = head->next;
        while(fast&&fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode * second_head = slow->next;
        slow->next = NULL;
        return merge( sortList(head) , sortList(second_head) );
    }
    ListNode * merge( ListNode * left , ListNode * right ){
        ListNode * new_list = new ListNode(0);
        ListNode * temp = new_list;
        while( left && right ){
            if( left->val < right->val ){
                temp=temp->next = left;
                left = left->next;
            }
            else{
                temp = temp->next = right;
                right = right->next;
            }
        }
        if( left ) temp->next = left;
        else temp->next = right;
        return new_list->next;
    }

};

效率就是最前面的runtime
当然merge函数也可以这样写，效率也一样的

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if( !head || !head->next ) return head;
        ListNode * slow = head;
        ListNode * fast = head->next;
        while(fast&&fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode * second_head = slow->next;
        slow->next = NULL;
        return merge( sortList(head) , sortList(second_head) );
    }
    ListNode * merge( ListNode * left , ListNode * right ){
        ListNode * new_list = new ListNode(0);
        ListNode * temp = new_list;
        while( left || right ){
            if( left && ( !right || left->val < right->val ) ){
                temp = temp->next = left;
                left = left->next;
            }
            if( right && ( !left || left->val >= right->val ) ){
                temp = temp->next = right;
                right = right->next;
            }
        }
        temp->next = NULL;
        return new_list->next;
    }

};

至于快速排序，有点难想，就贴一个网上的写法：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* tail;
        quickSort(head,tail);
        return head;
    }
private:
    void quickSort(ListNode* &head,ListNode* &tail){
        if(head==nullptr)
            return;
        ListNode left_head(-1),right_head(-1);
        ListNode *left_tail=&left_head,*right_tail=&right_head;
        ListNode *pivot_head=head,*pivot_tail=head,*now=head->next;
        int key=pivot_head->val;
        //paritition
        while(now!=nullptr){
            if(now->val < key){
                left_tail->next=now;
                left_tail=now;
            } else if(now->val > key){
                right_tail->next=now;
                right_tail=now;
            } else {
                pivot_tail->next=now;
                pivot_tail=now;
            }
            now=now->next;
        }

        //deal with end node
        right_tail->next=nullptr;
        left_tail->next=nullptr;
        pivot_tail->next=nullptr;

        quickSort(left_head.next,left_tail);
        quickSort(right_head.next,right_tail);
        //connect pivot,sorted left part,sorted right part
        if(left_head.next!=nullptr && right_tail!=&right_head){
            //left part and right part is not null
            //L->P->R
            left_tail->next=pivot_head;
            pivot_tail->next=right_head.next;
            head=left_head.next;
            tail=right_tail;

        } else if(left_head.next!=nullptr){
            //left part is not null but right part is null
            //L->P
            left_tail->next=pivot_head;
            head=left_head.next;
            tail=pivot_tail;
        } else if(right_tail!=&right_head){
            //right part is not null but left part is null
            //P->R
            pivot_tail->next=right_head.next;
            head=pivot_head;
            tail=right_tail;
        }
        //no need to deal with two null situation.
    }
};