/**

 * Merge sort use bottom-up policy,

 * so Space Complexity is O(1)

 * Time Complexity is O(NlgN)

 * stable sort

*/

/*

* 解决该题需要使用归并排序，而这里的归并排序需要使用自底向上策略；

这样才能实现，空间复杂度O(1)，时间复杂度O(NlgN)

*/

class Solution {

public:

    ListNode *sortList(ListNode *head) {

        if(!head || !(head->next)) return head;  // 判断传入的链表头结点是否为空或者链表是否只有一个元素

        //get the linked list's length

        // 下面代码将得到链表的长度

        ListNode* cur = head;

        int length = ;

        while(cur){

            length++;

            cur = cur->next;

        }

        //设定一个虚节点，并指向头结点，方便后续操作

        ListNode dummy();  // 我不太喜欢这么创建结点的方式，更喜欢如：ListNode* dummy = new ListNode(0)

        dummy.next = head;

        // 创建三个节点指针：left用来存放切分后第一部分链表的头结点，right用来存放第二部分的头结点，tail用来存放归并之后的有序链表的尾节点（方便下面的拼接）

        ListNode *left, *right, *tail;

        for(int step = ; step < length; step <<= ){  // 左移代表乘以2

　　　　　　　/**

　　　　　　　　* 初次遍历的时候，由于dummy.next等于头指针，所以cur初次的值是头指针；但是cur主要用来存放什么呢？

　　　　　　　　* 从下面的while循环可以看出端倪：每次都是以步长step为基准，对链表进行切分（split(left, step)），使链表分为两部分，前面的一部分包含step个元素；后面是剩下的链表（len - step个元素），对后面这个链表同理，也做了一次切分（split(right, step)），此时的最后一部分链表的头指针由cur来存放。

　　　　　　　　* 简单一句话：每一次while循环都需要切两次，而cur用来存放最后一次切分的剩下的链表的头结点。而剩下这部分链表是没有排序和归并的（还是杂乱无章）

　　　　　　　　* 此外，值得注意的是while循环在for循环里，也就是每一个step，链表都会遍历的执行，实现step内的元素有序。

　　　　　　　　* while循环将链表变成一段一段有序的了（step长度为一段）

　　　　　　　**/

            cur = dummy.next;

            tail = &dummy;

            while(cur){

                left = cur;

                right = split(left, step);

                cur = split(right,step);

                tail = merge(left, right, tail);

            }

        }

        return dummy.next;

    }

private:

    /**

     * Divide the linked list into two lists,

     * while the first list contains first n ndoes

     * return the second list's head

     */

    /*

    * split函数将链表分成两部分链表，

    * 第一部分链表分包含n个节点，函数最后返回第二部分链表的头结点

    */

    ListNode* split(ListNode *head, int n){

        //if(!head) return NULL;

        // 遍历到第n个节点，后面就可以实现将第n个节点和第n+1个节点断开

        for(int i = ; head && i < n; i++) head = head->next;  

        if(!head) return NULL;

        // 下面两行实现断开这个操作

        ListNode *second = head->next;

        head->next = NULL;

        return second;

    }

    /**

      * merge the two sorted linked list l1 and l2,

      * then append the merged sorted linked list to the node head

      * return the tail of the merged sorted linked list

     */

    /*

    * 将两个排好序的链表l1和l2进行合并

    * 然后将合并好的新链表连接到传入的head节点之后

    * 最后返回归并排序好后的有序链表的尾节点

    */

    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head){

        ListNode *cur = head;  // 这里的cur相当于下面一步步合并出来的有序链表的尾结点，去连接下一个该存放的节点，并更新

        while(l1 && l2){

            if(l1->val > l2->val){

                cur->next = l2;

                cur = l2;

                l2 = l2->next;

            }

            else{

                cur->next = l1;

                cur = l1;

                l1 = l1->next;

            }

        }

        cur->next = (l1 ? l1 : l2);  // 将还有元素的部分链表连接到后面

        while(cur->next) cur = cur->next;  // 得到尾结点

        return cur;

    }

};