Ask for suggestion


  • 5
    J

    Here is my solution. Merge sort. Pass OJ. I would like to ask for suggestion to further improve it. E.g. shorter code or simpler design. Thanks in advance.

    ListNode *merge(ListNode* l1, ListNode* l2, ListNode* h){
        ListNode* l=h;
        while(l1||l2){
            if(!l1){
                l->next=l2;
                l2=l2->next;
            }
            else if(!l2){
                l->next=l1;
                l1=l1->next;
            }
            else if(l1->val<l2->val){
                l->next=l1;
                l1=l1->next;
            }
            else {
                l->next=l2;
                l2=l2->next;
            }
            l=l->next;
        }
        return l;
    }
    
    ListNode* split(ListNode* h, int len){
        for(int i=1;i<len&&h!=NULL;i++){
            h=h->next;
        }
        if(!h) return NULL;
        ListNode* t=h->next;
        h->next=NULL;
        return t;
    }
    
    ListNode *sortList(ListNode *head) {
        ListNode n(0);
        n.next=head;
        int listlen=0;
        while(head){listlen++;head=head->next;}
        for(int len=1;len<listlen;len*=2){
            ListNode* t=n.next,*l1,*l2;
            ListNode* h=&n;
            while(t!=NULL){
                l1=t;
                l2=split(t,len);
                t=split(l2,len);
                ListNode* tail=merge(l1,l2,h);
                tail->next=t;
                h=tail;
            }
        }
        return n.next;
    }

  • 2
    P

    The code looks fine. There is nothing you can improve.

    As 1337c0d3r mentioned about the refactoring, I can give another version similar to yours.

    ListNode *merge(ListNode* l1, ListNode* l2, ListNode* h){
        ListNode* l=h;
        while(l1||l2){
            if(!l1 || l2 && l1->val>l2->val){
                l->next=l2;
                l2=l2->next;
            } else {
                l->next=l1;
                l1=l1->next;
            }
            l=l->next;
        }
        return l;
    }

  • 0

    Your code looks pretty good to me. Great use of dummy node to simplify the code by the way.

    The usual strategy to make your code more concise is to identify the code with common patterns. I see that in your merge method you have very similar logic across all four conditional statements. This is a good candidate for refactoring -- Extract the common logic out into a separate method.

    The more concise version (but harder to read) is to utilize a pointer to pointer. You can't use a pointer reference since C++ requires all reference be initialized when you declare it, while pointers allow you to bind the reference dynamically.

    Below is the revised merge method, see if you like it:

    ListNode *merge(ListNode* l1, ListNode* l2, ListNode* h){
        ListNode* l=h;
        ListNode **ref = NULL;
        while(l1||l2){
            if(!l1){
                ref = &l2;
            }
            else if(!l2){
                ref = &l1;
            }
            else if(l1->val<l2->val){
                ref = &l1;
            }
            else {
                ref = &l2;
            }
            l->next = *ref;
            *ref = (*ref)->next;
            l=l->next;
        }
        return l;
    }

  • 0
    C

    I use two array to track the head of each sub list. combine every two adjacent sublists and put the new head into l2. And swap l1 and l2. repeat this procedure until there is only one head point in l1. The space complexity is O(n).

    class Solution {
        public:
            ListNode *sortList(ListNode *head) {
                if(!head) return head;
                vector<ListNode *> *l1 = new vector<ListNode *>;
                vector<ListNode *> *l2 = new vector<ListNode *>;
                while(head){      // insert nodes into array
                    ListNode *tmp = head;
                    head = head->next;
                    tmp->next = NULL;
                    l1->push_back(tmp);
                }
                
                while(l1->size() > 1){
                    for(int i=0; i < l1->size()/2; i++)
                        l2->push_back( merge( (*l1)[2*i], (*l1)[2*i+1] ) );  // merge two sub link list
                    
                    if(l1->size()%2) l2->push_back( (*l1)[l1->size()-1] );  // handle odd number of nodes
                    swap(l1, l2);
                    l2->clear();
                }
                 ListNode *result = (*l1)[0];
                delete l1;
                delete l2;
                return result;
            }
            
            ListNode *merge(ListNode *l1, ListNode *l2){
                 ListNode *h = NULL;
                 ListNode **p = &h;
                 while(l1 && l2) {
                     if(l1->val < l2->val){
                        *p = l1;
                        l1 = l1->next;
                     }else {
                        *p = l2;
                        l2 = l2->next;
                     }
                     p = &((*p)->next);
                 }
                 if(l1) *p = l1;
                 else *p = l2;
                 return h;
            }
        };

  • 0

    wow, that seems like some pretty intensive pointer manipulation :) Care to explain how it works, maybe in a few sentences? Also, what is the space complexity?
    One minor note: Always a good practice to delete after you new'd something.


  • 0
    C

    I update my answer. Thanks for your advice.


  • 0

    Have you thought of how to optimize your approach to constant space complexity?


  • 0
    C

    I do not know. Do you have any idea?


  • 0
    J

    Thanks @porker2008, your code is shorter. The only thing I worry about is the execution of
    (!l1 || l2 && l1->val>l2->val) seems depend on different compiler. In some compiler, it might execute l2->val even l2 is NULL. (PS. I don't know whether the new C++11 standard has addressed this issue or not.)


  • 0
    J
     Thanks 1337c0d3r, this is better! Inspired by porker2008, how about we make it even more concise, but harder to read in this way :)
    
    ListNode *merge(ListNode* l1, ListNode* l2, ListNode* h){
        ListNode* l=h;
        ListNode **ref = NULL;
        while(l1||l2){
            ref=!l1?&l2:!l2?&l1:l1->val<l2->val?&l1:&l2;
            l->next = *ref;
            *ref = (*ref)->next;
            l=l->next;
        }
        return l;
    }

  • 0
    P

    Most of the modern compiler will execute from left to right and do optimization on the result.
    for example, f(x) && g(x) or f(x) || g(x), both will execute f(x) first. If f(x) returns true for f(x) || g(x), then g(x) will not be called. If f(x) return false for f(x) && g(x), then g(x) will not be called.


  • 0

    There is a fancy term -- it is called Short-circuit evaluation. And yes, it is supported in both C++ and Java.


Log in to reply
 

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