题目：
Sort a linked list in O(n log n) time using constant space complexity.
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if ( !head || !head->next ) return head;
ListNode dummy(-);
dummy.next = head;
ListNode *p1=&dummy, *p2=&dummy;
while ( p2 && p2->next && p2->next->next )
{
p1 = p1->next;
p2 = p2->next->next;
}
ListNode *h1 = Solution::sortList(p1->next);
p1->next = NULL;
ListNode *h2 = Solution::sortList(dummy.next);
return Solution::mergeTwo(h1, h2);
}
static ListNode* mergeTwo(ListNode *h1, ListNode *h2)
{
ListNode dummy(-);
ListNode *p = &dummy;
while ( h1 && h2 )
{
if ( h1->val<h2->val )
{
p->next = h1;
h1 = h1->next;
}
else
{
p->next = h2;
h2 = h2->next;
}
p = p->next;
}
p->next = h1 ? h1 : h2;
return dummy.next;
}
};
tips：
单链表时间要求O(nlongn) 且const extra space，可以选择归并排序（另，双向链表适合用快速排序）
第一次没有AC，原因是少考虑一种返回条件，即“head只有一个元素的时候需要直接返回”，修改之后第二次AC了。
===================================================
第二次过这道题，尝试着摸索写出来，一次AC了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head)
{
if ( !head ) return NULL;
if ( !head->next ) return head;
ListNode dummpy();
ListNode* p1 = &dummpy;
ListNode* p2 = &dummpy;
dummpy.next = head;
while ( p2 && p2->next )
{
p1 = p1->next;
p2 = p2->next->next;
}
ListNode* r = Solution::sortList(p1->next);
p1->next = NULL;
ListNode* l = Solution::sortList(dummpy.next);
return Solution::merge2SortedLists(l,r); }
static ListNode* merge2SortedLists(ListNode* p1, ListNode* p2)
{
ListNode head();
ListNode* p = &head;
while ( p1 && p2 )
{
if ( p1->val < p2->val )
{
p->next = p1;
p1 = p1->next;
}
else
{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
p->next = p1 ? p1 : p2;
return head.next;
}
};