fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct ListNode
  4. {
  5.     int value;
  6.     ListNode* next;
  7. };
  8.  
  9. typedef struct ListNode ListNode;
  10.  
  11. ListNode* head = NULL;
  12. ListNode* tail = head;
  13.  
  14. void append(int value)
  15. {
  16.     if(head)
  17.     {
  18.         ListNode* temp = new ListNode();
  19.         temp->value = value;
  20.         temp->next = NULL;
  21.         tail->next = temp;
  22.         tail = tail->next;
  23.     }
  24.     else
  25.     {
  26.         head = new ListNode();
  27.         head->value = value;
  28.         head->next = NULL;
  29.         tail = head;
  30.     }
  31. }
  32.  
  33. ListNode* middle()
  34. {
  35.     if(head==NULL || head->next==NULL)
  36.         return head;
  37.  
  38.     ListNode* fast = head;
  39.     ListNode* slow = head;
  40.  
  41.     while(fast->next!=NULL && fast->next->next!=NULL)
  42.     {
  43.         slow = slow->next;
  44.         fast = fast->next->next;
  45.     }
  46.     return slow;
  47. }
  48.  
  49. ListNode* middle(ListNode* left, ListNode* right)
  50. {
  51.     ListNode* fast = left;
  52.     ListNode* slow = left;
  53.  
  54.     while(fast->next!=right->next && fast->next->next!=right->next)
  55.     {
  56.         slow = slow->next;
  57.         fast = fast->next->next;
  58.     }
  59.     return slow;
  60. }
  61. void printList()
  62. {
  63.     ListNode* temp = head;
  64.     while(temp)
  65.     {
  66.         cout << temp->value << " ";
  67.         temp = temp->next;
  68.     }
  69.     cout << endl;
  70. }
  71. void printList(ListNode* head, ListNode* tail)
  72. {
  73.     ListNode* temp = head;
  74.     while(temp!=tail->next)
  75.     {
  76.         cout << temp->value << " ";
  77.         temp = temp->next;
  78.     }
  79.     cout << endl;
  80. }
  81. const int INF = 0x7f7f7f7f;
  82.  
  83. void Merge(ListNode* left, ListNode* mid, ListNode* right)
  84. {
  85.     // creating Left auxiliary List
  86.     ListNode* LeftHead = NULL;
  87.     ListNode* LeftTail = NULL;
  88.  
  89.     ListNode* leftIterator = left;
  90.  
  91.     while(leftIterator!=mid->next)
  92.     {
  93.         if(LeftHead==NULL)
  94.         {
  95.             LeftHead = new ListNode();
  96.             LeftHead->value = leftIterator->value;
  97.             LeftHead->next = NULL;
  98.             LeftTail = LeftHead;
  99.         }
  100.         else
  101.         {
  102.             ListNode* temp = new ListNode();
  103.             temp->value = leftIterator->value;
  104.             temp->next = NULL;
  105.             LeftTail->next = temp;
  106.             LeftTail = LeftTail->next;
  107.         }
  108.         leftIterator = leftIterator->next;
  109.     }
  110.  
  111.     ListNode* temp = new ListNode();
  112.     temp->value = INF;
  113.     temp->next = NULL;
  114.     LeftTail->next = temp;
  115.     LeftTail = LeftTail->next;
  116.  
  117.  
  118.     // creating Right auxiliary List
  119.     ListNode* RightHead = NULL;
  120.     ListNode* RightTail = NULL;
  121.  
  122.     ListNode* rightIterator = mid->next;
  123.  
  124.     while(rightIterator!=right->next)
  125.     {
  126.         if(RightHead==NULL)
  127.         {
  128.             RightHead = new ListNode();
  129.             RightHead->value = rightIterator->value;
  130.             RightHead->next = NULL;
  131.             RightTail = RightHead;
  132.         }
  133.         else
  134.         {
  135.             ListNode* temp = new ListNode();
  136.             temp->value = rightIterator->value;
  137.             temp->next = NULL;
  138.             RightTail->next = temp;
  139.             RightTail = RightTail->next;
  140.         }
  141.         rightIterator = rightIterator->next;
  142.     }
  143.  
  144.     temp = new ListNode();
  145.     temp->value = INF;
  146.     temp->next = NULL;
  147.     RightTail->next = temp;
  148.     RightTail = RightTail->next;
  149.  
  150.  
  151.     leftIterator = LeftHead;
  152.     rightIterator = RightHead;
  153.  
  154.     ListNode* temporaryHead = left;
  155.     ListNode* temporaryEnd = right;
  156.  
  157.     while(left!=right->next)
  158.     {
  159.         if(leftIterator->value<rightIterator->value)
  160.         {
  161.             left->value = leftIterator->value;
  162.             leftIterator = leftIterator->next;
  163.         }
  164.         else
  165.         {
  166.             left->value = rightIterator->value;
  167.             rightIterator = rightIterator->next;
  168.         }
  169.         left = left->next;
  170.     }
  171.  
  172.     return;
  173. }
  174.  
  175. void Msort(ListNode* left, ListNode* right)
  176. {
  177.     if(left!=right)
  178.     {
  179.         ListNode* mid = middle(left, right);
  180.         Msort(left, mid);
  181.         Msort(mid->next, right);
  182.         Merge(left, mid, right);
  183.     }
  184. }
  185.  
  186. void deleteList()
  187. {
  188.     while(head)
  189.     {
  190.         ListNode* temp = head;
  191.         head = head->next;
  192.         delete(temp);
  193.     }
  194.     return;
  195. }
  196.  
  197. int main()
  198. {
  199.     #ifdef TarekHasan
  200.         freopen("input.txt", "r", stdin);
  201.     #endif // TarekHasan
  202.  
  203.     int n; cin >> n;
  204.     while(n--)
  205.     {
  206.         int temp; cin >> temp;
  207.         append(temp);
  208.     }
  209.     printList();
  210.     Msort(head, tail);
  211.     printList();
  212.     deleteList();
  213.     return 0;
  214. }
  215.  
Success #stdin #stdout 0.01s 5416KB
comments (?)
stdin
copy 
15
90 63 25 14 10 21 35 69 27 85 99 987 125 325 654
stdout
copy 
90 63 25 14 10 21 35 69 27 85 99 987 125 325 654 
10 14 21 25 27 35 63 69 85 90 99 125 325 654 987
https://ideone.com/D8U0ay
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

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!