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

        auto dummy = new ListNode(-1);
        dummy->next = head;

        for (int i = 1; i < n; i <<= 1)     // i是每次归并段的区间长度  1,2,4,8..
        {
            auto cur = dummy;
            // j代表每一段的开始，每次将两段有序段归并为一个大的有序段，故而每次+2i
            for (int j = 1; j + i <= n; j += 2 * i)
            {
                auto p = cur->next, q = p;  // p表示第一段的起始点，q表示第二段的起始点
                // 让q移动到第二段的起始位置
                for (int k = 0; k < i; k ++ )   q = q->next;

                int x = 0, y = 0; // x,y用于计数第一段和第二段已经归并的节点个数
                // 由于当链表长度非2的整数倍时表长会小于i,故而需要加上p && q的边界判断
                while (x < i && y < i && p && q)
                {
                    if (p->val <= q->val)
                    {
                        cur->next = p;
                        cur = cur->next;
                        p = p->next;
                        x ++ ;
                    }
                    else
                    {
                        cur->next = q;
                        cur = cur->next;
                        q = q->next;
                        y ++ ;
                    }
                }

                while (x < i && p)
                {
                    cur->next = p;
                    cur = cur->next;
                    p = p->next;
                    x ++ ;
                }
                while (y < i && q)
                {
                    cur->next = q;
                    cur = cur->next;
                    q = q->next;
                    y ++ ;
                }

                // 退出while循环后 q指向的是下一链表的表头
                // 把排好序的链表尾链接到下一链表的表头
                cur->next = q;
            }
        }

        return dummy->next; // 返回排序好的链表
    }
};