Sort List

LeetCode #148

Description:

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

Example:

Note

Idea:

常数空间且 O(nlogn)，单链表适合用归并排序，双向链表适合用快速排序。本题可以复
用”Merge Two Sorted Lists” 的代码。

这个用的就是merge sort。

Code:

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;

        ListNode *slow=head;
        ListNode *fast=head;

        // Cannot use while(fast!=NULL && fast->next!=NULL)
        //这样不是平均分，如果list=[2,1]会造成dead loop
        while(fast->next!=NULL && fast->next->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }

        // Cut list into half
        fast=slow->next;
        slow->next=NULL;

        // Sort the first half and second half, then merge sorted list
        ListNode *sorted_head1 = sortList(head);
        ListNode *sorted_head2 = sortList(fast);
        return mergeTwoLists(sorted_head1, sorted_head2);
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL || l2==NULL) return l1==NULL? l2 : l1;
        ListNode dummy(-1);

        ListNode * curr = &dummy;
        while(l1!=NULL && l2!=NULL){
            if(l1->val<=l2->val){
                curr->next=l1;
                l1=l1->next;
            }
            else{
                curr->next=l2;
                l2=l2->next;
            }
            curr=curr->next;
        }

        curr->next = l1==NULL? l2: l1;

        return dummy.next;
    }
};