链表排序（常数级空间复杂度）

花了一晚上都没整明白，细节太重要啦！！！

里面的几个步骤都是难点：
1.自底向上思想；
2.断链
3.归并
4.合链

涉及到的指针操作&&边界条件多，一不小心就入坑了。。。

不过归根结底，还是自己太菜啊。。
呜呜

//
// Created by jt on 2020/8/8.
// 循环实现：不会超时
//
/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode *sortList(ListNode *head) {
        // write code here
        // 要点：bottom-to-up；断链操作；合并操作（重新链接）
        if (!head || !head->next) {
            return head;
        }
        ListNode dummy(0);
        dummy.next = head;
        auto p = head;
        // 开始bottom-to-up
        int size = 1;
        while (p->next) {
            ++size;
            p = p->next;
        }
        for (int step = 1; step < size; step <<= 1) {
            auto curHead = dummy.next;
            auto tail = &dummy;
            while (curHead) {
                auto left = curHead;
                auto right = cut(left, step);  // left->@->@ right->@->@->@...
                curHead = cut(right, step);    // left->@->@ right->@->@ curHead->@->...
                tail->next = merge(left, right);
                while (tail->next) {
                    tail = tail->next;
                }
            }
        }
        return dummy.next;
    }
    ListNode* cut(ListNode *left, int step) {
        ListNode *p = left;
        // 找到左链最后一个节点
        while (--step && p) {
            p = p->next;
        }
        // 如果左链节点数不够
        if (!p) return nullptr;
        auto next = p->next;
        p->next = nullptr;          // 断链
        return next;
    }
    ListNode *merge(ListNode *left, ListNode *right) {
        ListNode dummy(0);
        ListNode *head = &dummy;
        while (left && right) {
            if (left->val > right->val) {
                head->next = right;
                head = right;
                right = right->next;
            } else {
                head->next = left;
                head = left;
                left = left->next;
            }
        }
        head->next = left ? left : right;
        return dummy.next;
    }
};