Problem:

Sort a linked list in O(n log n) time using constant space complexity.

解题思路:

首先，时间复杂度能达到O(nlgn)的排序算法，常见的有3种:堆排序、归并排序和快速排序，

而对于链表，用堆排序显然不太可能，所以，我们可用归并或者是快排.由于合并两个链表，只用

修改相应的指针，所以其能做到空间复杂度O(1).下面是利用归并排序思想实现的链表排序.

解题思路:

class Solution {
public:
    ListNode *sortList(ListNode *p) 
    {
        if (p == NULL || p->next == NULL)
            return p;
        //加入一个头节点，避免合并时讨论rear为空的情况.
        ListNode *head = new ListNode(-1), *q = head;
        head->next = p;
        int cnt = 0;
        while (p)
        {
            ++cnt;
            p = p->next;
            if (cnt % 2 == 0)
                q = q->next;
        }
        p = q->next, q->next = NULL;
        //递归进行左右两支排序
        head->next = q = sortList(head->next);
        p = sortList(p);
        //合并
        q = Merge(head, p);
        free(head);
        return q;        
    }
    ListNode* Merge(ListNode *head, ListNode *r)
    {
        ListNode *l = head->next, *rear = head;
        while (l && r)
        {
            if (l->val < r->val)
            {
                rear->next = l;
                l = l->next, rear = rear->next;
            }
            else
            {
                rear->next = r;
                r = r->next, rear = rear->next;
            }
        }
        while (l)
        {
            rear->next = l;
            l = l->next, rear = rear->next;
        }
        while (r)
        {
            rear->next = r;
            r = r->next, rear = rear->next;
        }
        return head->next;
    }
};