sundeepblue
3/10/2014 - 11:27 AM

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

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

ListNode *mergeSort(ListNode *head) {
    if(!head || !head->next) return head;
    // get middle node
    // not right if write: *fast = head. Otherwise, {2,1} will not be sorted.
    ListNode *slow = head, *fast = head->next; 
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *left = head, *right = slow->next;
    slow->next = NULL;
    left = mergeSort(left);
    right = mergeSort(right);
    return merge(left, right);
}

ListNode *merge(ListNode *L, ListNode *R) {
    if(!L) return R;
    if(!R) return L;
    ListNode *h = NULL;
    if(L->val < R->val) {
        h = L;
        h->next = merge(L->next, R);
    } else {
        h = R;
        h->next = merge(L, R->next);
    }
    return h;
}