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. int main()
  187. {
  188.     #ifdef TarekHasan
  189.         freopen("input.txt", "r", stdin);
  190.     #endif // TarekHasan
  191.  
  192.     int n; cin >> n;
  193.     while(n--)
  194.     {
  195.         int temp; cin >> temp;
  196.         append(temp);
  197.     }
  198.     printList();
  199.     Msort(head, tail);
  200.     printList();
  201.     return 0;
  202. }
  203.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
10
5 6 2 1 3 5 4 7 8 9
stdout
copy 
5 6 2 1 3 5 4 7 8 9 
1 2 3 4 5 5 6 7 8 9
https://ideone.com/rBazDs
Merge Sort in Singly Linked List
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!