Advertisement
Rohit4Pal

Untitled

May 21st, 2022
727
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ListNode* mergeLL(ListNode* h1,ListNode *h2){
  2.    
  3.     ListNode *head=NULL,*p=h1,*q=h2,*curr=NULL;
  4.     while(p!=NULL && q!=NULL){
  5.         if(p->data <q->data){
  6.             if(head==NULL){
  7.                 head=new ListNode(p->data);
  8.                 curr=head;
  9.             }else{
  10.                 curr->next=new ListNode(p->data);
  11.                 curr=curr->next;
  12.             }
  13.             p=p->next;
  14.         }else{
  15.             if(head==NULL){
  16.                 head=new ListNode(q->data);
  17.                 curr=head;
  18.             }else{
  19.                 curr->next=new ListNode(q->data);
  20.                 curr=curr->next;
  21.             }
  22.             q=q->next;
  23.         }
  24.     }
  25.    
  26.     while(p != NULL){
  27.         curr->next=new ListNode(p->data);
  28.         curr=curr->next;
  29.         p=p->next;
  30.     }
  31.    
  32.     while(q != NULL){
  33.         curr->next=new ListNode(q->data);
  34.         curr=curr->next;
  35.         q=q->next;
  36.     }
  37.     return head;
  38. }
  39.  
  40. ListNode* mergeSort(ListNode* head) {
  41.    
  42.     if(head==NULL || head->next == NULL)
  43.         return head;
  44.    
  45.     ListNode *slow=head,*fast=head;
  46.     while(fast->next != NULL && fast->next->next != NULL){
  47.         slow=slow->next;
  48.         fast=fast->next->next;
  49.     }
  50.    
  51.     ListNode *temp=slow;
  52.     slow=slow->next;
  53.     temp->next = NULL;
  54.    
  55.     ListNode *h1=mergeSort(head);
  56.     ListNode *h2=mergeSort(slow);
  57.     head= mergeLL(h1,h2);
  58.    
  59.     return head;
  60. }
Advertisement
RAW Paste Data Copied
Advertisement