Two different solutions well-commented in C accepted as best


  • 3
    //AC - 20ms;
    struct ListNode* merge(struct ListNode* l, struct ListNode* r)
    {
        struct ListNode head;
        struct ListNode* p = &head;
        while(l && r)
        {
            if(l->val <= r->val) //collect left first when left and right are equal;
            {
                p->next = l;
                l = l->next;
            }
            else
            {
                p->next = r;
                r = r->next;
            }
            p = p->next;
        }
        p->next = (l == NULL ? r : l);
        return head.next; //return without the fake head;
    }
    struct ListNode* sortList(struct ListNode* head)
    {
        if(head == NULL || head->next == NULL)
            return head;
        struct ListNode *s1 = head, *s2 = head->next;
        while(s2 && s2->next) //split the list into two halves;
        {
            s1 = s1->next;
            s2 = s2->next->next;
        }
        s2 = s1->next;
        s1->next = NULL;
        return merge(sortList(head), sortList(s2)); //merge two parts by invoking recursive method;
    }
    

    struct ListNode* partition(struct ListNode* head, struct ListNode* tail)
    {
        if(head == tail || head->next == tail)
            return head;
        int pivot = head->val;
        struct ListNode left, mid, right; //the head of each position;
        struct ListNode *l=&left, *m=&mid, *r=&right; //used to move forward;
        while(head != tail)
        {
            if(head->val < pivot)
            {
                l->next = head;
                l = l->next;
            }
            else if(head->val > pivot)
            {
                r->next = head;
                r = r->next;
            }
            else
            {
                m->next = head;
                m = m->next;
            }
            head = head->next;
        }
        r->next = tail; //connect the right end to the next part;
        m->next = partition(right.next, tail);  //connect the middle part to the right;
        l->next = mid.next; //connect the left to the middle;
        return partition(left.next, l->next); //handle the left part and return the head of the left;
    }
    
    
    //AC - 16ms;
    struct ListNode* swiftSort(struct ListNode* head)
    {
        return partition(head, NULL);
    }

  • 0
    A

    @LHearen Both are recursive. Neither satifies the "constant space complexity" requirement.


  • 0

    @ayuanx You are almost right about that. But to make the code simple to avoid bottom-up method, here I'd prefer to use top-down one. Of course, thank you for your pointing it out.


  • 1

    @LHearen Why "almost" right? They're just right.


  • 1
    A

    @LHearen If the problem doesn't say "must use constant space", then your solutions are all good.
    But in interview, if the interviewer says "must use constant space", your recursive solution will get 0 point. Yeah I know it is fussy, but interviewers are like gods in such scenarios.


  • 0

    @StefanPochmann Yes, you're right about this. Sorry for the word used in the previous post. I will try to make up another version to solve this problem A.S.A.P. Thank you, guys!


  • 1
    A

    @LHearen I am not against anybody. Yes I am aware that my words could be misleading sometimes. That's because it is my habit to say it when I see it in the first place.


  • 0

    @ayuanx It's fine, buddy. You're efficient type caring about the result. Huhhuh, nice to have you in Leetcode. Have fun!


Log in to reply
 

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