在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)了。
