思路

1. 本题要求时间复杂度为$O(nlogn)$ 空间复杂度为$O(1)$
2. merge(l1,l2) 传统归并的空间复杂度为$O(n)$
3. cut(l1,n) 返回的切掉从l1开始数n个节点以后，后半部分链的头结点
4. 先两两归并，再4个为一组归并，不断倍增组内元素的size
5. bottom-to-up
6. 本代码要烂熟于心

代码

/**
 * 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:
    //要求时间复杂度Onlogn 空间复杂度O1
    ListNode* sortList(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        auto p = head;
        int length = 0;
        while(p){
            length++;
            p = p->next;
        }
        for(int size = 1 ;size < length ; size <<= 1){
            auto cur = dummy->next;
            auto tail = dummy;
            while(cur){
                auto left = cur;
                auto right = cut(left,size);
                cur = cut(right,size);
                tail->next = merge(left,right);
                while(tail->next) tail = tail->next;
            }
        }
        return dummy->next;
    }
    ListNode* cut(ListNode* head , int n){
        auto p = head;
        while(--n && p){
            p = p->next;
        }
        if(!p) return nullptr;
        auto next = p->next;
        p->next = nullptr;
        return next;
    }
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode* dummy = new ListNode(0);
        auto p = dummy;
        while(l1 && l2){
            if(l1->val < l2->val){
                p->next = l1;
                p = l1;
                l1 = l1->next;
            }
            else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return dummy->next;
    }
};