fork download
copy 
  1. #include <algorithm>
  2. #include <exception>
  3. #include <iostream>
  4. #include <list>
  5.  
  6.  
  7. struct node {node * next; int val;};
  8.  
  9.  
  10. void destroy(node* n)
  11. {
  12.     while (n != nullptr) {
  13.         auto next = n->next;
  14.         delete n;
  15.         n = next;
  16.     }
  17. }
  18.  
  19. node* create(const std::list<int>& l)
  20. {
  21.     if (l.empty()) { return nullptr; }
  22.  
  23.     node* root = nullptr;
  24.     node* last = root;
  25.  
  26.     for (auto e : l) {
  27.         node* n = new node();
  28.         n->next = nullptr;
  29.         n->val = e;
  30.  
  31.         if (root == nullptr) {
  32.             root = n;
  33.             last = root;
  34.         } else {
  35.             last->next = n;
  36.             last = n;
  37.         }
  38.     }
  39.     return root;
  40. }
  41.  
  42. bool is_sorted(const node* n) {
  43.     const node* cur = n;
  44.     const node* next = cur->next;
  45.  
  46.     while (next != nullptr && cur->val < next->val) {
  47.         cur = next;
  48.         next = next->next;
  49.     }	
  50.     return next == nullptr;	
  51. }
  52.  
  53. node* extract(node*& root, node* prev, node* n)
  54. {
  55.     if (prev == nullptr)
  56.     {
  57.         if (root == nullptr) {
  58.             return nullptr;   
  59.         }
  60.         root = n->next;
  61.         n->next = nullptr;
  62.         return n;
  63.     }
  64.     prev->next = prev->next->next;
  65.     n->next = nullptr;
  66.     return n;
  67. }
  68.  
  69. node* detach(node*& root)
  70. {
  71.     if (root == nullptr || root->next == nullptr) {
  72.         throw std::runtime_error("too short list");
  73.     }
  74.     node* prev = nullptr;
  75.     node* cur = root;
  76.     node* next = cur->next;
  77.  
  78.     while (next != nullptr && cur->val < next->val) {
  79.         prev = cur;
  80.         cur = next;
  81.         next = next->next;
  82.     }
  83.     if (next == nullptr) {
  84.         throw std::runtime_error("already sorted list");
  85.     }
  86.     if (!is_sorted(next)) {
  87.         throw std::runtime_error("not 'partially' sorted list");
  88.     }
  89.     if (next->next == nullptr || next->next->val < cur->val) {
  90.         return extract(root, prev, cur);
  91.     } else {
  92.         return extract(root, cur, next);
  93.     }
  94. }
  95.  
  96. void test(std::list<int> l)
  97. {
  98.     node* root = create(l);
  99.     node* n = nullptr;
  100.     try {
  101.         n = detach(root);
  102.         std::cout << n->val << std::endl;
  103.         if (!is_sorted(root)) {
  104.             throw std::runtime_error("result not sorted");
  105.         }
  106.     } catch (const std::exception& e) {
  107.         std::cout << e.what() << std::endl;
  108.     }
  109.     destroy(root);
  110.     destroy(n);
  111. }
  112.  
  113. int main() 
  114. {
  115.     test({1}); // too short list
  116.     test({1, 2, 3}); // already sorted list
  117.     test({1, 3, 2, 0}); // not partially sorted list
  118.  
  119.     test({3, 1}); // 3 or 1 (currently 3)
  120.     test({3, 1, 5}); // 1
  121.     test({1, 4, 2, 10}); // 4 or 2 (currently 2)
  122.     test({28, 144, 44, 52, 60}); // 144
  123.     test({60, 68, 76, 84, 65, 100}); // 65
  124. }
  125.  
  126.  
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
too short list
already sorted list
not 'partially' sorted list
3
1
2
144
65
https://ideone.com/kx276l
language:
C++14 (gcc 8.3)
created:
7 years 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!