148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Total Accepted: 94368
Total Submissions: 342453
Difficulty: Medium
Contributors: Admin

分析

首先可以使用和147相同的思想，把数字复制到vector<int> 中，然后排序，再赋值回去

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode * p = head;
        vector<int> list;
        while(p != NULL){
            list.push_back(p->val);
            p = p->next;
        }
        sort(list.begin(), list.end());
        p = head;
       for(auto n : list){
           p->val = n;
           p = p->next;
       }
       return head;
    }
     
};

如果需要对list本身进行操作，则需要使用时间复杂度O(NlogN),那么能用到的排序只有

快排，归并，堆排

1. 因为list是单向的没法从后往前，所以需要快排的话，只能重新建立一个倒序的list，进行快排，平均时间复杂度O(NlogN)，空间复杂度O(N)。下面的算法建立一个存储 ListNode * 的 vector 数组，从而实现双向访问

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL) return head;
        ListNode * p = head;
        vector<ListNode *> plists;
        int len = 0;
        while(p != NULL){
            ++len;
            plists.push_back(p);
            p = p->next;
        }
         
        // quick sort
        listQsort(plists, 0, len - 1);
         
        return head;
    }
    void listQsort(vector<ListNode *> &plists, int left, int right){
        if(left >= right) return;
        int i = left, j = right;
        int key = plists[i + (j - i) / 2]->val;
        while(i <= j){
            while(i <= j && plists[i]->val < key) ++i;
            while(i <= j && plists[j]->val > key) --j;
            if(i <= j){
                int tmp = plists[i]->val;
                plists[i++]->val = plists[j]->val;
                plists[j--]->val = tmp;
            }
        }
        listQsort(plists, left, j);
        listQsort(plists, i, right);
    }
     
};

2. 归并排序，需要使用快慢指针，找到中间node位置，如果使用递归的话，需要考虑栈的消耗空间，所以时间复杂度O(NlogN)，空间复杂度O(logN)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
         
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* pre = head;
        while(fast != NULL && fast->next != NULL){
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        /**如果这样写
         * ListNode* h2 = sortList(slow->next);
         * slow->next = NULL;
         * ListNode* h1 = sortList(head);
         * 会导致当list中只剩两个node，会永远死循环，不断递归调用下去
         */
        pre->next = NULL;
        ListNode* h1 = sortList(head);
        ListNode* h2 = sortList(slow);
         
        return mergeList(h1, h2);
    }
     
    ListNode* mergeList(ListNode* l1, ListNode* l2){
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        ListNode * head = NULL;
        if(l1->val < l2->val){
            l1->next = mergeList(l1->next, l2);
            head = l1;
        }
        else{
            l2->next = mergeList(l1, l2->next);
            head = l2;
        }
        return head;
    }
};

3. 堆排序，需要建立一个最小堆，空间复杂度O(N)，时间复杂度O(NlogN)

现在看来满足常量空间的只能是2，归并排序并将其写成非递归形式。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
         
        ListNode* p = head;
        int len = 0;
        while(p != NULL){
            p = p->next;
            ++len;
        }
         
        ListNode dummy(0);
        dummy.next = head;
        for(int i = 1; i < len; i = i << 1){// 每次步长 翻倍
            ListNode* cur = dummy.next;
            ListNode* tail = &dummy, * left, * right;
            while(cur != NULL){
                left = cur;
                right = split(left, i);
                cur = split(right, i);
                tail = mergeList(left, right, tail);
            }
        }
        return dummy.next;
    }
     
    /**
     * split l + step sublist
     * return this sublist's next node
     * 
     **/
    ListNode* split(ListNode * l, int step){
        ListNode * pre;
        while(l != NULL && step--){
            pre = l;
            l = l->next;
        }
        if(l != NULL){
            pre->next = NULL;
        }
        return l;
    }
     
    /**
     * merge l1 and l2, then attach the new list to head->next
     * return the tail of the new list
     * 
     **/
    ListNode* mergeList(ListNode* l1, ListNode* l2, ListNode* head){
        ListNode dummy(0);
        ListNode * p = &dummy;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                p->next = l1;
                l1 = l1->next;
            }
            else{
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        if(l1 == NULL) p->next = l2;
        if(l2 == NULL) p->next = l1;
        while(p->next != NULL) p = p->next;
        head->next = dummy.next;
        return p;
    }
};

null