Partition list Simple Solution in O(n) time


  • 0
    H

    The Solution is goes as follows:
    First we find the last node pointer.Now we will check for the first element which is less then x if the current node has the value that is equal to or larger than x then we will link this node at the end of the link which is very simple cause we have the last node pointer. We will check the element till the current not equal to the last node pointer.
    Now when we get the head which is less than x now we check after the head node and check whether they are less than or greater and equal to x if they are greater or equal than we have to link the node at the end of the list till the current pointer not equal to the last node pointer.
    Now we have to check only for the last node if it is equal and greater or less. If it is less then there is no need to do any thing but if it is larger or equal then we have to move at the end of the link list.
    The code is as follows:

    struct ListNode* partition(struct ListNode* head, int x) {
        
        struct ListNode *p,*pq;
        pq=NULL;    
        for(p=head;p!=NULL;p=p->next)
            pq=p;
        
        p=pq;
        
        //printf("%d",p->val);
        struct ListNode *q=pq;
        
        struct ListNode *ptr=head;
        
        
       // printf("%d",ptr->val);
        for(ptr=head; ptr!=NULL && ptr->val>=x && ptr!=q;)
        {
            
            if(ptr->val>=x)
            {
                struct ListNode *temp=ptr;
                if(ptr==head)
                {
                    head=head->next;
                }
                ptr=ptr->next;
                p->next=temp;
                temp->next=NULL;
                p=p->next;
            }
            else
                ptr=ptr->next;
        }
        
       // printf("%d",head->val);
        
        if(head!=q)
        {
            //printf("%d",ptr->val);
            struct ListNode *pre=ptr;
            ptr=ptr->next;
            
            for(;ptr!=q;)
            {
                if(ptr->val>=x)
                {
                    struct ListNode *temp=ptr;
                    ptr=ptr->next;
                    pre->next=temp->next;
                    temp->next=NULL;
                    p->next=temp;
                    p=p->next;
                }
                else
                {
                    pre=pre->next;
                    ptr=ptr->next;
                }
                
            }
            
            if(ptr->val>=x && ptr->next!=NULL)
            {
                pre->next=ptr->next;
                ptr->next=NULL;
                p->next=ptr;
                p=p->next;
            }
            
        }
        else
        {
            if(head!=NULL && head->val>=x)
            {
                struct ListNode *temp=head;
                p->next=temp;
                head=head->next;
                temp->next=NULL;
                p=p->next;
            }
        }
        
        return head;
        
    }
    
    

Log in to reply
 

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