?

?

Sort List

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

?

?

// 归并排序法：在动手之前一直觉得空间复杂度为常量不太可能，因为原来使用归并时，都是 O(N)的，需要复制出相等的空间来进行赋值归并。对于链表，实际上是可以实现常数空间占用的。

?

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if(!head||!head->next)
            return head;
        return mergeSort(head);
    }
    ListNode * mergeSort(ListNode *head){
        if(!head||!head->next)   //just one element
            return head;
        ListNode *p=head, *q=head, *pre=NULL;
        while(q&&q->next!=NULL){
            q=q->next->next;
            pre=p;
            p=p->next;  //divide into two parts
        }
        pre->next=NULL;
        ListNode *lhalf=mergeSort(head);
        ListNode *rhalf=mergeSort(p);  //recursive
        return merge(lhalf, rhalf);   //merge
    }
    ListNode * merge(ListNode *lh, ListNode *rh){
        ListNode *temp=new ListNode(0);
        ListNode *p=temp;
        while(lh&&rh){
            if(lh->val<=rh->val){
                p->next=lh;
                lh=lh->next;
            }
            else{
                p->next=rh;
                rh=rh->next;
            }
            p=p->next;
        }
        if(!lh)
            p->next=rh;
        else
            p->next=lh;
        p=temp->next;
        temp->next=NULL;
        delete temp;
        return p;
    }
};

?