题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解析

链表版自底向上的归并排序
简单说就是，先1个和1个合并，再2个和2个
自底向上省去了划分的过程（实际上没起任何作用），直接开始合并
具体实现时将整体链表一段一段的切开，每两个调用一次合并链表的merge函数

代码

/**
 * 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* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        int sz = 1;
        while(true){
            ListNode *pre = dummyHead, *cur = pre;
            while(cur->next){
                cur = pre;
                for(int i = 0; i < sz && cur->next; i ++, cur = cur->next);
                if(cur->next){
                    ListNode* pre2 = cur;
                    for(int i = 0; i < sz && cur->next; i ++, cur = cur->next);
                    ListNode* next = cur->next, *head2 = pre2->next;
                    pre2->next = NULL, cur->next = NULL;
                    ListNode* tail;
                    pre->next = merge(pre->next, head2, tail);
                    pre = tail;
                    pre->next = next;
                }
                else if(pre == dummyHead){
                    sz = 0;
                    break;
                }
            }
            if(sz == 0 || cur == dummyHead) break;
            else sz *= 2;
        }
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
private:
    ListNode* merge(ListNode* a, ListNode* b, ListNode* &tail){
        ListNode* dummyHead = new ListNode(-1);
        ListNode *p1 = a, *p2 = b, *p = dummyHead;
        while(p1 && p2)
            if(p1->val < p2->val){
                p->next = p1;
                p1 = p1->next;
                p = p->next;
                p->next = NULL;
            }
            else{
                p->next = p2;
                p2 = p2->next;
                p = p->next;
                p->next = NULL;
            }
        if(p1) p->next = p1;
        if(p2) p->next = p2;
        tail = p;
        while(tail->next) tail = tail->next;
        ListNode* ret = dummyHead->next;
        delete dummyHead;
        return ret;
    }
};