题目来源
Sort a linked list in O(n log n) time using constant space complexity.
排序题目，还是链表，看着题目我陷入了沉思，直接用插入排序可以吗？试一下吧

    ListNode* sortList(ListNode* head) {
        if (!head)
            return head;
        ListNode *newHead = new ListNode(0);
        ListNode *pre = newHead;
        ListNode *cur = head;
        ListNode *next = NULL;
        while (cur) {
            next = cur->next;
            while (pre->next && pre->next->val < cur->val) {
                pre = pre->next;
            }
            cur->next = pre->next;
            pre->next = cur;
            pre = newHead;
            cur = next;
        }
        return newHead->next;
    }

然后发现不出意料的TLE，超时了！我该怎么办？好吧，答案是归并排序，我已经忘了有这么一个东西，就是分成两堆两两排序再合并那种算法。

    ListNode* sortList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode *p1 = head, *p2 = head->next;
        while (p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }
        p2 = p1->next;
        p1->next = NULL;
        ListNode *list1 = sortList(head);
        ListNode *list2 = sortList(p2);
        return merge(list1, list2);
    }
    
    ListNode* merge(ListNode* list1, ListNode* list2)
    {
        ListNode *newHead = new ListNode(0);
        ListNode *cur = newHead;
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1;
                list1 = list1->next;
            }
            else {
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }
        if (list1)
            cur->next = list1;
        if (list2)
            cur->next = list2;
        return newHead->next;
    }