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

示例 1:

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

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

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        int n = 0;
        for (auto *p = head; p; p = p->next) n++;

        auto *dummy = new ListNode(-1);
        dummy->next = head;
        for (int len = 1; len < n; len *= 2) {
            auto *begin = dummy;
            for (int j = 0; j + len < n; j += len * 2) {//每一段合并
                //定位合并链表的头节点
                auto *left= begin->next, *right = left;
                for (int k = 0; k < len; k++) right = right->next;
                // 归并排序
                int l = 0, r = 0;
                while (l < len || r < len && right)
                    if (!(r < len && right) || l < len && left->val <= right->val) {
                        begin = begin->next = left;
                        left = left->next;
                        l++;
                    } else {
                        begin = begin->next = right;
                        right = right->next;
                        r++;
                    }
                begin->next = right;
            }
        }
        return dummy->next;
    }
};