spider68

merge sort doubly linked list

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