单链表排序

以arr = [8,6,7,5,1,2]为例

1. 自顶向下归并排序（递归）——分治法

Time: O(NlogN)
Space: O(LOG(N))

• 自顶向下：

(8->6->7) | (5->1->2)
(8->6)|(7) | (5->1)|(2)
(8)|(6)|(7) |(5)|(1)|(2)

• 栈返回：

(6->8)|(7) |（1->5) | (2)
(6->7->8) | (1->2->5)
(1->2->5->6->7->8)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }
        ListNode* slow = head, *fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* right = slow->next;
        slow->next = nullptr;
        ListNode* left = head;
        ListNode* sortedLeft = sortList(left), *sortedRight = sortList(right);
        return merge(sortedLeft, sortedRight);        
    }

    ListNode* merge(ListNode* left, ListNode* right){
        ListNode dummyNode(0), *cur = &dummyNode;
        while(left && right){
            if(left->val < right->val){
                cur->next = left;
                left = left->next;
                cur = cur->next;
            }else{
                cur->next = right;
                right = right->next;
                cur = cur->next;
            }
        }
        cur->next = left ? left : right;
        return dummyNode.next;
    }
};

2. 自底向上归并排序 （空间O(1)）

Time: O(NLogN)
Space: O(1)

• 切分归并过程

step = 1: dummy->(8->6->7->5->1->2)
step = 1: dummy->(6->8) | (7->5->1->2)
step = 1: dummy->(6->8->5->7) (1->2)
step = 1: dummy->(6->8->5->7->1->2)
step = 2: dummy->(5->6->7->8) | (1->2)
...
dummy->(1->2->5->6->7->8)

• 返回 dummy->next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next){ return head; }
        int length = 0;
        ListNode* cur = head;
        while(cur){
            cur = cur->next;
            length++;
        }
        ListNode newNode(0);
        newNode.next = head;
        for(int step = 1; step < length; step <<= 1){
            ListNode* pre = &newNode;
            cur = newNode.next;
            while(cur){
                ListNode* left = cur;
                ListNode* right = cutList(left, step);
                cur = cutList(right, step);
                pre->next = mergeList(left, right);
                while(pre->next){
                    pre = pre->next;
                }
            }
        }
        return newNode.next;

    }

    ListNode* cutList(ListNode* cur, int step){
        for(int i = 1; (i < step) && cur; ++i){
            cur = cur->next;
        }
        if(!cur) return nullptr;
        ListNode* nextNode = cur->next;
        cur->next = nullptr;
        return nextNode;
    }

    ListNode* mergeList(ListNode* left, ListNode* right){
        ListNode dummyNode(0), *cur = &dummyNode;
        while(left && right){
            if(left->val < right->val){
                cur->next = left;
                left = left->next;
            }else{
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = left ? left : right;
        return dummyNode.next;
    }
};

3. 快速排序（元素个数较多且基本有序的情况下可能超时）

Time: worst case, O(N^2)
Space: O(N)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode dummyNode(0);
        dummyNode.next = head;
        quickSort(&dummyNode, head, nullptr);
        return dummyNode.next;
    }

    void quickSort(ListNode* dummyNode, ListNode* head, ListNode* end){
        if(head != end){
            ListNode* pivot = getPivot(dummyNode, head);
            quickSort(dummyNode, dummyNode->next, pivot);
            quickSort(pivot, pivot->next, end);
        }
    }

    ListNode* getPivot(ListNode* dummyNode, ListNode* head){
        ListNode nodeR(0), nodeL(0);
        ListNode* cur = head->next, *pRight = &nodeR, *pLeft = &nodeL;
        int pivot = head->val;
        while(cur){
            if(cur->val < pivot){
                pLeft->next = cur;
                pLeft = pLeft->next;
            }else{
                pRight->next = cur;
                pRight = pRight->next;
            }
            cur = cur->next;
        }
        pRight->next = nullptr;
        head->next = nodeR.next;
        pLeft->next = head;
        dummyNode->next = nodeL.next;
        return dummyNode->next;
    }
};