My O(n log n) time, O(1) space solution


  • 51
    V

    Nice problem. I use a non-recurisve way to write merge sort.
    For example, the size of ListNode is 8,

    Round #1 block_size = 1

    (a1, a2), (a3, a4), (a5, a6), (a7, a8)

    Compare a1 with a2, a3 with a4 ...

    Round #2 block_size = 2

    (a1, a2, a3, a4), (a5, a6, a7, a8)

    merge two sorted arrays (a1, a2) and (a3, a4), then merge tow sorted arrays(a5, a6) and (a7, a8)

    Round #3 block_size = 4

    (a1, a2, a3, a4, a5, a6, a7, a8)

    merge two sorted arrays (a1, a2, a3, a4), and (a5, a6, a7, a8)

    No need for round #4 cause block_size = 8 >= n = 8

    class Solution {
    public:
        int count_size(ListNode *node){
            int n = 0;
            while (node != NULL){
                node = node->next;
                ++n;
            }
            return n;
        }
        ListNode *sortList(ListNode *head) {
            int block_size = 1, n = count_size(head), iter = 0, i = 0, a = 0, b = 0;
            ListNode virtual_head(0);
            ListNode *last = NULL, *it = NULL, *A = NULL, *B = NULL, *tmp = NULL;
            virtual_head.next = head;
            while (block_size < n){
                iter = 0;
                last = &virtual_head;
                it = virtual_head.next;
                while (iter <  n){
                    a = min(n - iter, block_size);
                    b = min(n - iter - a, block_size);
                    
                    A = it;
                    if (b != 0){
                        for (i = 0; i < a - 1; ++i) it = it->next;
                        B = it->next;
                        it->next = NULL;
                        it = B;
                        
                        for (i = 0; i < b - 1; ++i) it = it->next;
                        tmp = it->next;
                        it->next = NULL;
                        it = tmp;
                    }
                    
                    while (A || B){
                        if (B == NULL || (A != NULL && A->val <= B->val)){
                            last->next = A;
                            last = last->next;
                            A = A->next;
                        } else {
                            last->next = B;
                            last = last->next;
                            B = B->next;
                        }
                    }
                    last->next = NULL;
                    iter += a + b;
                }
                block_size <<= 1;
            }
            return virtual_head.next;
        }
    };

  • 0
    S

    can you give a explanation of your below code:
    what's a b here for?
    a = min(n - iter, block_size);
    b = min(n - iter - a, block_size);

                if (b != 0){ //what's the mean, if b != 0
                    for (i = 0; i < a - 1; ++i) it = it->next;
                    B = it->next;
                    it->next = NULL;
                    it = B;
    
                    for (i = 0; i < b - 1; ++i) it = it->next;
                    tmp = it->next;
                    it->next = NULL;
                    it = tmp;
                }
    
                while (A || B){ //also here??
                    if (B == NULL || (A != NULL && A->val <= B->val)){
                        last->next = A;
                        last = last->next;
                        A = A->next;
                    } else {
                        last->next = B;
                        last = last->next;
                        B = B->next;
                    }
                }
                last->next = NULL;
                iter += a + b;

  • 0
    V

    When merge two sorted lists, the lengths of two lists are a and b. when b != 0 we need to find the begin of the next two lists to be sorted. A||B means that we still need to merge them while list A or list B is not NULL. If A == NULL ,the list A has already added to the new list.


  • 0
    S

    but, what the mean of iter, i saw every loop the iter will add a+b. and what's your method to calculate a and b?
    a = min(n - iter, block_size);
    b = min(n - iter - a, block_size);


  • 0
    V

    a and b suppose to be blocksize, but it may do not have enough numbers to do. for example n = 10, blocksize = 4. first a = 4, b = 4, then iter = 8. next round, a should be 4, but only remain n - iter = 2 numbers. Therefore a = 2. Use the same way to calculate b.


  • 0
    Z

    I think your enough explanation should be added in your code,you will get it


  • 0
    W

    comment retracted . neat solution ...


  • 0
    M

    Very nice solution. I think this line is unnecessary:

    last->next = NULL;


  • 0
    E

    Good idea!!!


  • 0
    C

    Wow, it is really a clever solution!


  • 0
    K

    Great Idea!!!


  • 0
    C

    I can't understand your code.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.