Linked List that is Sorted Alternatingly

#1

quesrtion–>
https://practice.geeksforgeeks.org/problems/linked-list-that-is-sorted-alternatingly/1/?category[]=Linked%20List&category[]=Linked%20List&problemStatus=unsolved&difficulty[]=0&page=1&query=category[]Linked%20ListproblemStatusunsolveddifficulty[]0page1category[]Linked%20List#
code–>


Showing TLE help!!

#2

Hey @sheikhhaji18

prev1->next=NULL;//added

    prev2->next=NULL;//added

    temp2=reverse(temp2);

    prev1->next=temp2;

    *head= temp1;
#3

hey my aprroach was wrong i just seperating the ll, then linked them together,still they may be not sorted,but then i reversed the descending the ll, and merged the two sorted linkedlist and it got accepted.(got idea from gfg)

Node* reverse(Node* head){
    Node* c=head;
    Node* n=NULL;
    Node* p=NULL;
    while(c!=NULL){
        n=c->next;
        c->next=p;
        p=c;
        c=n;
    }
    // head=p;
    return p;
}
Node* merge(Node* a,Node* b){
    if(a==NULL){
        return b;
    }
    if(b==NULL){
        return a;
    }
    Node* c=NULL;
    if(a->data<b->data){
        c=a;
        c->next=merge(a->next,b);
        return c;
    }
    else{
        c=b;
        c->next=merge(a,b->next);
        return c;
    }
}
void sort(Node **head)
{
    if((*head)==NULL){
        return;
    }
    if((*head)->next==NULL){
        return;
    }
     Node* temp1=(*head);
     
     Node* temp2=(*head)->next;
     Node* prev1=temp1;
     Node* prev2=temp2;
     Node* temp3=temp2->next;
     temp1->next=NULL;
     temp2->next=NULL;
     bool isodd=1;
     while(temp3!=NULL){
         if(isodd){
             prev1->next=temp3;
             prev1=temp3;
             
             temp3=temp3->next;
             prev1->next=NULL;
         }
         else{
             prev2->next=temp3;
             prev2=temp3;
             temp3=temp3->next; 
             prev2->next=NULL;
         }
         isodd=!isodd;
     }
     prev1->next=NULL;
     prev2->next=NULL;
     
     if(temp2->data>temp2->next->data){
         temp2=reverse(temp2);
     }
     else{
         temp1=reverse(temp2);
     }
     
    Node* n=merge(temp1,temp2);
    (*head)=n;
}
1 Like