fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. template <class T>
  6. class Chain;
  7.  
  8. template<class T>
  9. class ChainNode {
  10.     friend class Chain<T>;
  11. private:
  12.     T data;
  13.     ChainNode<T>* link;
  14. };
  15.  
  16. template <class T>
  17. class Chain {
  18. public:
  19.     Chain() { first = nullptr; }
  20.     ~Chain();
  21.  
  22.     bool isEmpty() const { return first == nullptr; }
  23.     int Length() const;
  24.     bool Find(int k, T& x) const;
  25.     int Search(const T& x) const;
  26.     Chain<T>& Insert(int k, const T& x);
  27.     Chain<T>& Delete(int k, T& x);
  28.     void Output(ostream& out) const;
  29.     Chain<T>& RK(int k);         // Function for Partially reversing the list
  30.  
  31. private:
  32.     ChainNode<T>* first;
  33.     int listSize=0;
  34. };
  35.  
  36. template <class T>
  37. Chain<T>::~Chain() {
  38.     ChainNode<T>* next;
  39.     while (first) {
  40.         next = first->link;
  41.         delete first;
  42.         first = next;
  43.     }
  44. }
  45.  
  46. template <class T>
  47. int Chain<T>::Length() const {
  48.     return listSize;
  49. }
  50.  
  51. template <class T>
  52. bool Chain<T>::Find(int k, T& x) const {
  53.     if (k <= 0 || k > listSize) {
  54.         return false;
  55.     }
  56.     ChainNode<T>* current = first;
  57.     for (int i = 1; i < k; i++) {
  58.         current = current->link;
  59.     }
  60.     x = current->data;
  61.     return true;
  62. }
  63.  
  64. template <class T>
  65. int Chain<T>::Search(const T& x) const {
  66.     ChainNode<T>* current = first;
  67.     int i = 1;
  68.     while (current != nullptr && current->data != x) {
  69.         current = current->link;
  70.         i++;
  71.     }
  72.     if (current == nullptr) {
  73.         return -1;
  74.     }
  75.     else {
  76.         return i;
  77.     }
  78. }
  79.  
  80. template <class T>
  81. Chain<T>& Chain<T>::Insert(int k, const T& x) {
  82.     if (k < 0 || k > listSize) {
  83.         cout << "Invalid position to insert" << endl;
  84.         return *this;
  85.     }
  86.     ChainNode<T>* y = new ChainNode<T>;
  87.     y->data = x;
  88.     if (k == 0 || isEmpty()) {
  89.         y->link = first;
  90.         first = y;
  91.     }
  92.     else {
  93.         ChainNode<T>* p = first;
  94.         for (int i = 1; i < k; i++) {
  95.             p = p->link;
  96.         }
  97.         y->link = p->link;
  98.         p->link = y;
  99.     }
  100.     listSize++;
  101.     return *this;
  102. }
  103.  
  104. template <class T>
  105. Chain<T>& Chain<T>::Delete(int k, T& x) {
  106.     if (k < 1 || k > listSize) {
  107.         cout << "Invalid position to delete" << endl;
  108.         return *this;
  109.     }
  110.     ChainNode<T>* p = first;
  111.     if (k == 1) {
  112.         first = first->link;
  113.     }
  114.     else {
  115.         ChainNode<T>* prev = nullptr;
  116.         for (int i = 1; i < k; i++) {
  117.             prev = p;
  118.             p = p->link;
  119.         }
  120.         prev->link = p->link;
  121.     }
  122.     x = p->data;
  123.     delete p;
  124.     listSize--;
  125.     return *this;
  126. }
  127.  
  128. template <class T>
  129. void Chain<T>::Output(ostream& out) const {
  130.     ChainNode<T>* p = first;
  131.     while (p != nullptr) {
  132.         out << p->data << " ";
  133.         p = p->link;
  134.     }
  135. }
  136.  
  137. // Function for partially reversing the linked list
  138. template <class T>
  139. Chain<T>& Chain<T>::RK(int k) {
  140.     if (k < 1 || k > listSize) {
  141.         cout << "Invalid value of k, no change in list" << endl;
  142.         return *this;
  143.     }
  144.  
  145.     ChainNode<T>* prev = nullptr;
  146.     ChainNode<T>* current = first;
  147.     ChainNode<T>* next = nullptr;
  148.     ChainNode<T>* subend = nullptr;
  149.     ChainNode<T>* subend2 = nullptr;
  150.  
  151.     int count2 = 0;
  152.  
  153.     // Reversing every k-th segment
  154.     for (int i = 0; i <= listSize; i += k) {
  155.         int count = 0;
  156.         if (count2 % 2 == 0 && count2 > 1) {
  157.             subend->link = prev;
  158.         } else if (count2 % 2 != 0 && count2 > 2) {
  159.             subend2->link = prev;
  160.         }
  161.  
  162.         if (count2 % 2 == 0) subend = current; else subend2 = current;
  163.  
  164.         if ((listSize - i) < k && (listSize - i) != 0) break;
  165.  
  166.         prev = nullptr;
  167.         next = nullptr;
  168.  
  169.         while (current && count < k) {
  170.             next = current->link;
  171.             current->link = prev;
  172.             prev = current;
  173.             current = next;
  174.             count++;
  175.         }
  176.  
  177.         // Resetting first
  178.         if (i == 0) first = prev;
  179.         count2++;
  180.     }
  181.  
  182.     // Joining the remaining elements
  183.     if (next) {
  184.         if (subend == next) subend2->link = next; else subend->link = next;
  185.     }
  186.     return *this;
  187. }
  188.  
  189. int main() {
  190.     Chain<int> mylist;
  191.  
  192.     // Inserting elements
  193.     mylist.Insert(0, 1); 
  194.     mylist.Insert(1, 2); 
  195.     mylist.Insert(2, 3); 
  196.     mylist.Insert(3, 4); 
  197.     mylist.Insert(4, 5); 
  198.     mylist.Insert(5, 6); 
  199.     mylist.Insert(6, 7);
  200.     mylist.Insert(7,8);
  201.     mylist.Insert(8,9);
  202.     mylist.Insert(9,10);
  203.     mylist.Insert(10,11);
  204.     mylist.Insert(11,12);
  205.     mylist.Insert(12,13);
  206.  
  207.     cout << "Original List: ";
  208.     mylist.Output(cout);
  209.     cout << endl;
  210.     int k = 4;
  211.     mylist.RK(k);
  212.     if (k<1 || k>mylist.Length()) return 0;
  213.     cout << "List after reversing every kth segment of the list with k=" << k << ": ";
  214.     mylist.Output(cout);
  215.     cout << endl;
  216.  
  217.     return 0;
  218. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original List: 1 2 3 4 5 6 7 8 9 10 11 12 13 
List after reversing every kth segment of the list with k=4: 4 3 2 1 8 7 6 5 12 11 10 9 13
https://ideone.com/ivLgF7
language:
C++ 4.3.2 (gcc-4.3.2)
created:
33 days 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!