8 ms C++ solution with explanation


  • 0
    L

    Algorithm :

    1. Take two vectors v1(for collecting node values < x) and v2(for collecting values >= x).
    2. Traverse through the link list and fill the vectors based on value.
    3. Now, traverse through the list again and change the node values with the value in v1
    4. Once done with v1, start filling the value from v2

    Complexity : O(N).

    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            
            int size=0;
            ListNode *temp=head,*start=NULL;
            vector<int> before,after;
            
            
            // Check for corner cases in which list if NULL or number of elements is zero.
            if((head==NULL) || (head->next==NULL))
                return head;
            
        // Create two vectors(before and after) to store the value less than and greater than x respectively. 
            while(temp)
            {
                if(temp->val<x)
                    before.push_back(temp->val);
                else 
                    after.push_back(temp->val);
                    
                temp = temp->next;
            }
            
        // Start from the beginning and change the value in the original list with the values present in the first vector(before)
            temp = head;
            size = before.size();
            
            for(int i=0;i<size;i++)
            {
              temp->val = before[i];
              temp = temp->next;
            }
          
        // Now update the remaining list pointers with the second vector (after) i.e all value greater thn or equals to x. 
            size=after.size();
            for(int i=0;i<size;i++)
            {
                temp->val = after[i];
                temp = temp->next;
            }
            
            return head;
        }
    };

Log in to reply
 

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