O(nlgn)时间排序链表

在O(nlgn)时间里面对链表排序，且使用特定的空间。看到这个时间很容易想到的是快排，堆排，归并排序这几个时间复杂度满足条件的排序。但是快排是建立在容器可以有随机存取的能力上的，链表显然不具有，那么我们就此想到堆排序和归并。堆排序我忘了，但是归并是会的。有一点是归并虽然时间是满足的，但是要有O(n)的空间去存放。想到我们这里是链表，我们只要改变指针就可以达到这种效果，那么我们就使用归并排序试一下。
归并排序需要不断的二分链表知道单个cell，然后再组合起来。我们怎么二分链表呢，很好搞，用快慢指针来搞。好了基本思想就是这样，代码实现起来。

class Solution
{
public:
    ListNode* sortlist(ListNode* head)
    {
        if(!head || !head->next)
            return head;
        ListNode* p = head,*q = head->next;
        //为什么q初始的时候要设置成phead->next呢，考虑只有两个节点的情况
        while(q&&q->next)
        {
            p = p->next;
            q = q->next->next;//
        }
        ListNode* left = sortlist(p->next);
        p->next = NULL;
        ListNode* right = sortlist(head);
        return merge(left,right);
    }

    ListNode* merge(ListNode* left,ListNode * right)
    {
        ListNode dummy(0);
        ListNode* p = &dummy;
        while(left&&right)
        {
            if(left->val < right->val)
            {
                p->next = left;
                left = left->next;
            }
            else
            {
                p->next = right;
                right = right->next;
            }
            p = p->next;
        }
        if(left) p->next = left;
        if(right) p->next = right;
        return dummy.next;
    }
}

代码就是这样的，那么我发现一个问题，每次merge的时候都要申请一个node，这样的merge上来需要的空间不也是O(n)了。