spider68

merge sort linked list

May 18th, 2020
202
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1.  Node* merge( Node* a , Node* b){
  2.     Node* result = NULL;
  3.     if (a == NULL)
  4.         return (b);
  5.     else if (b == NULL)
  6.         return (a);
  7.  
  8.     if (a->data <= b->data) {
  9.         result = a;
  10.         result->next = Merge(a->next, b);
  11.     }
  12.     else {
  13.         result = b;
  14.         result->next = Merge(a, b->next);
  15.     }
  16.     return (result);
  17.     }
  18.  
  19.    Node* sortList(Node* head) {
  20.         if(!head || !head->next) return head;
  21.         Node* slow = head;
  22.         Node* fast =head->next;
  23.         while(fast && fast->next){        
  24.             fast= fast->next->next;
  25.             slow = slow->next;
  26.         }
  27.         Node* headb = slow->next;    
  28.         slow->next = NULL;                
  29.         return merge(sortList(head) , sortList(headb));
  30.         }
Add Comment
Please, Sign In to add comment