Simple c++ Solution


  • 2
    M

    The idea is to keep adding the nodes to two different list which I have maintained it as head1 and head2.
    Head1 list contains the value which are smaller than x and head 2 which has greater than or equal to x.
    temp1 and temp2 are used to keep track of the last element that has been added to the end . We traverse the given input list and keep changing the next pointer accordingly. At the end if there were no elements in head 1 we just return head2, otherwise we link the list head1(smaller elemets) to head2 and return head1

    class Solution {
    public:
    ListNode* partition(ListNode* head, int x) {

        if(head == NULL)
            return head;
            
        ListNode *head1=NULL,*temp1,*head2=NULL,*temp2;
        ListNode *curr=head;
        
        while(curr!=NULL){
            if(curr->val<x){
                //for the list with smaller than number
                if(head1 == NULL){
                    //checking condition if the first element of this list
                    head1=curr;
                    curr=curr->next;
                    temp1=head1;
                    
                }else{
                    temp1->next=curr;
                    curr=curr->next;
                    temp1=temp1->next;
                    }
                
            }else{
                //for the list with greater than or equal to number
                if(head2 == NULL){
                    //checking condition if the first element of this list
                    head2=curr;
                    curr=curr->next;
                    temp2=head2;
                    temp2->next=NULL;
                    
                }else{
                    temp2->next=curr;
                    curr=curr->next;
                    temp2=temp2->next;
                    temp2->next=NULL;
                }
                
            }
        }
        if(head1!=NULL ){
            temp1->next = head2;
            return head1;
        }else if(head2!=NULL){
              return head2;
        }
        
    }
    

    };


Log in to reply
 

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