In-place solution c++


  • 1

    The idea is, move the no smaller part as a group (sub-list).

    1->3->1->4->1->1->5
    ||
    ------------------------
    1->3->1->4->1->1->5
       ||
    ------------------------
    1->3->1->4->1->1->5
       |  |
    ------------------------
    1->1->3->4->1->1->5
          ||
    ------------------------
    1->1->3->4->1->1->5
          |  |
    ------------------------
    1->1->3->4->1->1->5
          |     |
    ------------------------
    1->1->1->3->4->1->5
             |     |
    ------------------------
    1->1->1->1->3->4->5
                |     |
    

    So, first swap 3 with 1, then 34 with 1, next swap 345 with something, ...
    Code if needed:

    ListNode* partition(ListNode* head, int x) {
        ListNode* dummy= new ListNode(0);
        dummy->next=head;
        ListNode *h=dummy,*t1,*t2;
        while (h->next && h->next->val < x) h=h->next;
        t1=h;t2=h->next;
        while (t2){
            while (t2 && t2->val >=x){
                t1=t1->next;
                t2=t2->next;
            }
            if (t2){
                t1->next=t2->next;
                t2->next=h->next;
                h->next=t2;
                h=h->next;
                t2=t1->next;
            }
        }
        return dummy->next;
    }

Log in to reply
 

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