fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node{
  5.   int val;
  6.   Node *next;
  7. };
  8.  
  9. class List{
  10.     public:
  11.     Node *head, *tail;
  12.  
  13.     List(){
  14.         head = tail = NULL;
  15.     }
  16.  
  17.     Node *getNode(int &data){
  18.         Node *nn = new Node;
  19.         nn->val = data;
  20.         nn->next = NULL;
  21.         return nn;
  22.     }
  23.  
  24.     void insertNode(int &data){
  25.         if(!head){
  26.             head = tail = getNode(data);
  27.             return;
  28.         }
  29.  
  30.         tail->next = getNode(data);
  31.         tail = tail->next;
  32.     }
  33.  
  34.     void mergeSort() {
  35.         head = mergeSortHelper(head);
  36.     }
  37.  
  38.     Node *mergeSortHelper(Node *start){
  39.         if(start && start->next){
  40.  
  41.             Node *mid = divideList(start);
  42.  
  43.             Node *first = mergeSortHelper(start);
  44.             Node *second = mergeSortHelper(mid);
  45.  
  46.             return mergeListsRecur(NULL, first, NULL, second);
  47.         }
  48.         else{
  49.             return start;
  50.         }
  51.     }
  52. /*========================== Iterative Merge =============================*/  
  53.     Node *mergeListsIter(Node* head1, Node* head2) {
  54.  
  55.         if(!head1)
  56.             return head2;
  57.  
  58.         if(!head2)
  59.             return head1;
  60.  
  61.         Node *c1 = head1, *c2 = head2, *p1=NULL, *p2=NULL;
  62.  
  63.         while(c1 && c2){
  64.             if(c1->val > c2->val){
  65.  
  66.                 if(!p1 && !p2){
  67.                     p2 = c2;
  68.                     c2 = c2->next;
  69.  
  70.                     p2->next = c1;
  71.                     p1 = p2;
  72.                     p2 = NULL;
  73.  
  74.                     head1 = p1;
  75.                 }
  76.                 else if(!p2){
  77.                     p2 = c2;
  78.                     c2 = c2->next;
  79.  
  80.                     p2->next = c1;
  81.                     p1->next = p2;
  82.                     p1 = p2;
  83.                     p2 = NULL;
  84.                 }
  85.             }
  86.             else{
  87.                 p1 = c1;
  88.                 c1 = c1->next;
  89.             }
  90.         }
  91.  
  92.         if(!c1 && c2){
  93.             p1->next = c2;
  94.             c2 = NULL;
  95.         }
  96.  
  97.         return head1;
  98.     }
  99. /*========================== Iterative Merge =============================*/  
  100.  
  101. /*========================== Recursive Merge =============================*/  
  102.     Node *mergeListsRecur(Node *p1, Node *h1, Node* p2, Node *h2){
  103.  
  104.         if(!p1 && !h1)
  105.             return h2;
  106.  
  107.         if(!p2 && !h2)
  108.             return h1;
  109.  
  110.         if(p1 && !h1){
  111.             p1->next = h2;
  112.             return NULL;
  113.         }
  114.  
  115.         if(p2 && !h2){
  116.             return NULL;
  117.         }
  118.  
  119.         Node *start = NULL;
  120.  
  121.         if(h1->val > h2->val){
  122.             Node *nxt = h2->next;
  123.             h2->next = h1;
  124.  
  125.             if(!p1 && !p2){
  126.                 start = h2;
  127.             }
  128.             else if(!p2){
  129.                 p1->next = h2;
  130.             }
  131.  
  132.             mergeListsRecur(h2, h1, p2, nxt);
  133.         }
  134.         else{
  135.             mergeListsRecur(h1, h1->next, p2, h2);    
  136.         }
  137.  
  138.         return start ? start : h1;
  139.     }
  140. /*========================== Recursive Merge =============================*/  
  141.  
  142.     Node *divideList(Node *ptr){
  143.         Node *prev = NULL, *slow = ptr, *fast = ptr;
  144.  
  145.         while(fast && fast->next){
  146.             prev = slow;
  147.             slow = slow->next;
  148.             fast = fast->next->next;
  149.         }
  150.  
  151.         if(prev)
  152.             prev->next = NULL;
  153.  
  154.         return slow;
  155.     }
  156.  
  157.     void printList(){
  158.         Node *curr = head;
  159.  
  160.         while(curr){
  161.             cout<<curr->val;
  162.             curr = curr->next;
  163.  
  164.             if(curr)
  165.             	cout<<"->";
  166.         }
  167.     }
  168. };
  169.  
  170. int main() {
  171.     int n;
  172.     cin>>n;
  173.  
  174.     int data;
  175.  
  176.     List lst;
  177.  
  178.     for(int i = 0; i < n; ++i){
  179.         cin>>data;
  180.         lst.insertNode(data);
  181.     }
  182.  
  183.     lst.mergeSort();
  184.  
  185.     lst.printList();
  186.  
  187.     return 0;
  188. }
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
6
3 7 10 1 4 5
stdout
copy 
1->3->4->5->7->10
https://ideone.com/UbiSjb
Merge sort linked list with iterative and recursive merge
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!