Solution In Place


  • 0
    Z
    /*
     * find the first element >= 'x',
     * the element after it whose val < x will insert before the first elemt >= 'x'
     * O(n)
     */
    class Solution {
    public: // tail insert x times ,each time inset smallest
        ListNode* partition(ListNode* head, int x) {
            ListNode *pre_p = NULL, * p =head;
            while(p != NULL){  // find first >= 'x' pivot
                if(p -> val >= x)break;
                else {pre_p = p; p = p-> next;}
            }
            if(p == NULL)return head;//not find ,it means all the element < x
            ListNode *pre = p,*cur = p -> next;
            while(cur != NULL){    // traverse to cope with the elements after the pivot
                if(cur-> val < x){
                    pre -> next =cur -> next;
                    if(pre_p == NULL){head= cur;cur -> next = p;}
                    // if the head`s vale > x, the head is pivot
                    else{
                        cur -> next =pre_p -> next;
                        pre_p -> next = cur;
                    }
                    pre_p = cur;
                    cur = pre -> next;
                }
                else {pre = cur; cur = cur -> next;}
            }
            return head;
        }
    };
    

Log in to reply
 

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