Add additional

8 files changed, 415 insertions, 2 deletions

diff --git a/Additional/README.md b/Additional/README.md
new file mode 100644
index 0000000..96b8018
--- /dev/null
+++ b/Additional/README.md
@@ -0,0 +1,68 @@
+# Задачи за допълнително упражнение 22.11.2022
+
+## Задача първа - Merge linked lists
+Да се напише функция, която получава два сортирани списъка с елементи цели числа, обединява ги в един сортиран списък и връща резултата.
+
+**Пример:**
+
+Вход:
+* l1 = [1, 2, 4, 8, 16]
+* l2 = [1, 2, 3, 5, 7, 9, 11]
+
+Изход:
+
+* [1, 1, 2, 2, 3, 4, 5, 7, 8, 9, 11, 16]
+
+## Задача втора
+Даден е едносвъран списък, чийто елементи са числа. Напишете функция rearange, която пренарежда елементите, така че първо да бъдат четните числа, после нечетните. Относителната наредба между числата трябва да се запази. Решението ви трябва да работи за O(n) време и O(1) памет.
+
+Пример: 
+
+Вход: 
+
+* 3 -> 5 -> 2 -> 9 -> 4
+
+Изход: 
+
+* 2 -> 4 -> 3 -> 5 -> 9
+
+## Задача трета
+Даден е свързан списък, чиито елементи са числа. Напишете функция oddEvenList, която пренарежда списъка така, че в първо да бъдат възлите на нечетни **позиции** а след това тези на четни. Решението ви трябва да работи в O(n) време и O(1) памет. Считаме първата позиция за нечетна.
+
+Пример:
+
+Вход:
+* 1 -> 2 -> 3 -> 4 -> 5
+
+Изход:
+* 1 -> 3 -> 5 -> 2 -> 4
+
+Вход:
+* 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
+
+Изход:
+* 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
+
+## Задача четвърта - Reverse nodes in K-group
+Да се напише функция, която приема едносвързан списък и естествено число k. За k знаем, че е по - голямо от 0, но по - малко от дължината на списъка. K група наричаме възлите на индекси [0..k-1], [k..2k-1] и тн. Да се обърнат всички K групи.
+
+Пример:
+
+Вход: [1, 2, 3, 4, 5], k = 2
+
+Тук K групите са (1, 2), (3, 4). В резултата те са обърнати.
+
+Изход: [2, 1, 4, 3, 5]
+
+Вход: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], k = 4
+
+Тук K групите са (1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16). В резултата те са обърнати.
+
+Изход: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13, 17]
+
+## Задача пета
+Нека е даден списък L с елементи стекове. Възлите на L са от тип Node<std::stack>. Да се дефинира подходящо параметризирана функция equalize(L), която размества елементите на стековете така, че да няма два стека в L с разлика в броя на елементите, по-голяма от 1.
+
+## Задача шеста
+Даден е свързан списък с една връзка L, чийто елементи са опашки.
+Да се напише функция, което конкатенира всички последователни опашки, чиито елементи отговарят на даден предикат p.
\ No newline at end of file
diff --git a/Additional/concatenate-queues.cpp b/Additional/concatenate-queues.cpp
new file mode 100644
index 0000000..c3f772e
--- /dev/null
+++ b/Additional/concatenate-queues.cpp
@@ -0,0 +1,70 @@
+#include"../Seminar04/linked-list-utils.h"
+#include<iostream>
+#include<queue>
+
+using ListNode = LinkedListNode<std::queue<int>>;
+
+void concatenate(std::queue<int>& to, std::queue<int>& from) {
+    while(!from.empty()) {
+        to.push(from.front());
+        from.pop();
+    }
+}
+
+bool all(std::queue<int> q, bool (*pred)(int)) {
+    while(!q.empty()) {
+        if(!pred(q.front())) {
+            return false;
+        }
+        q.pop();
+    }
+
+    return true;
+}
+
+void concatenateSimilarQueues(ListNode* ll, bool (*pred)(int)) {
+    if(!ll || !ll->next)
+        return;
+
+    ListNode* iter = ll;
+
+    while(iter && iter->next) {
+        if(all(iter->data, pred)) {
+            while(iter->next && all(iter->next->data, pred)) {
+                ListNode* toDelete = iter->next;
+                iter->next = iter->next->next;
+                concatenate(iter->data, toDelete->data);
+
+                delete toDelete;
+            }
+        }
+        iter = iter->next;
+    }
+}
+
+void printQueue(std::queue<int> q) {
+    std::cout << "[ ";
+    while(!q.empty()) {
+        std::cout << q.front() << " ";
+        q.pop();
+    }
+    std::cout << " ]" << std::endl;
+}
+
+int main() {
+    ListNode* ll = fromList({
+        std::queue<int>({1, 2, 3}),
+        std::queue<int>({4, 5, 6, 7, 8, 8, 9}),
+        std::queue<int>({12, 14, 16}),
+        std::queue<int>({101, 102}),
+        std::queue<int>({103, 104, 105})
+    });
+
+    concatenateSimilarQueues(
+        ll,
+        [](int x) -> bool { return x < 10 || x > 100; }
+    );
+
+    printLinkedList(ll, printQueue);
+    freeList(ll);
+}
\ No newline at end of file
diff --git a/Additional/equalize.cpp b/Additional/equalize.cpp
new file mode 100644
index 0000000..263ccd2
--- /dev/null
+++ b/Additional/equalize.cpp
@@ -0,0 +1,60 @@
+#include<iostream>
+#include"../Seminar04/linked-list-utils.h"
+#include<stack>
+
+using ListNode = LinkedListNode<std::stack<int>>;
+
+// O(k*n) памет, където n е дължината на списъка а k размера на най - големия стек
+// O(k*n) време
+void equalize(ListNode* ll) {
+    std::stack<int> temp;
+    ListNode* iter = ll;
+
+    while(iter) {
+        while(!iter->data.empty()) {
+            temp.push(iter->data.top());
+            iter->data.pop();
+        }
+        iter = iter->next;
+    }
+
+    iter = ll;
+
+    while(!temp.empty()) {
+        if(iter == nullptr) {
+            iter = ll;
+        }
+        iter->data.push(temp.top());
+        temp.pop();
+        iter = iter->next;
+    }
+}
+
+void printStack(std::stack<int> s) {
+    int size = s.size();
+
+    std::cout << "[";
+
+    while (!s.empty()) {
+        std::cout << s.top() << " ";
+        s.pop();
+    }
+
+    std::cout << "] -> " << size << std::endl;
+}
+
+int main() {
+    ListNode* ll = fromList(
+        {
+            std::stack<int>({1, 4}), 
+            std::stack<int>({6, 7, 8, 9, 5}), 
+            std::stack<int>({10, 11, 12}), 
+            std::stack<int>({1, 41}), 
+            std::stack<int>({6, 7, 8, 9, 5, 7, 9, 0, 10, 20, 30})
+        }
+    );
+    
+    equalize(ll);
+    printLinkedList(ll, printStack);
+    freeList(ll);
+}
\ No newline at end of file
diff --git a/Additional/merge-sorted.cpp b/Additional/merge-sorted.cpp
new file mode 100644
index 0000000..b801a72
--- /dev/null
+++ b/Additional/merge-sorted.cpp
@@ -0,0 +1,51 @@
+#include<iostream>
+#include"../Seminar04/linked-list-utils.h"
+
+using ListNode = LinkedListNode<int>;
+
+ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
+    if(list1 == nullptr)
+        return list2;
+
+    if(list2 == nullptr)
+        return list1;
+
+    ListNode* start = nullptr;
+    ListNode* iter = nullptr;
+
+    while(list1 != nullptr && list2 != nullptr) {
+        ListNode*& toInsert = (list1->data > list2->data) ? list2 : list1;
+
+        if(iter == nullptr) {
+            start = toInsert;
+            iter = toInsert;
+        }
+        else {
+            iter->next = toInsert;
+            iter = iter->next;
+        }
+
+        toInsert = toInsert->next;
+    }
+
+    ListNode* rest = (list1 == nullptr) ? list2 : list1;
+
+    while(rest != nullptr) {
+        iter->next = rest;
+        iter = iter->next;
+        rest = rest->next;
+    }
+
+    iter->next = nullptr;
+    return start;
+}
+
+int main() {
+    ListNode* l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
+    ListNode* l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
+    
+    ListNode* r = mergeTwoLists(l1, l2);
+    
+    printLinkedList(r);
+    freeList(r);
+}
\ No newline at end of file
diff --git a/Additional/oddEvenList.cpp b/Additional/oddEvenList.cpp
new file mode 100644
index 0000000..05a95ac
--- /dev/null
+++ b/Additional/oddEvenList.cpp
@@ -0,0 +1,55 @@
+#include"../Seminar04/linked-list-utils.h"
+
+using ListNode = LinkedListNode<int>;
+
+ListNode* oddEvenList(ListNode* head) {
+    if(head == nullptr || head->next == nullptr)
+        return head;
+    
+    ListNode* oddStart = nullptr;
+    ListNode* oddIter = nullptr;
+    
+    ListNode* evenStart = nullptr;
+    ListNode* evenIter = nullptr;
+    
+    bool odd = true;
+    
+    while(head) {
+        ListNode*& curr = odd ? oddIter : evenIter;
+        
+        if(curr == nullptr) {
+            curr = head;
+            if(odd) 
+                oddStart = head; 
+            else
+                evenStart = head;
+        }
+        else {
+            curr->next = head;
+            curr = curr->next;
+        }
+        
+        head = head->next;
+        odd = !odd;
+    }
+    
+    oddIter->next = evenStart;
+    
+    if(evenIter != nullptr)
+        evenIter->next = nullptr;
+    
+    return oddStart;
+}
+
+int main() {
+    ListNode* l = fromList({1, 2, 3, 4, 5});
+    
+    ListNode* result = oddEvenList(l);
+    printLinkedList(result);
+    freeList(result);
+
+    ListNode* ls = fromList({2, 1, 3, 5, 6, 4, 7});
+    result = oddEvenList(ls);
+    printLinkedList(result);
+    freeList(result);
+}
\ No newline at end of file
diff --git a/Additional/rearange.cpp b/Additional/rearange.cpp
new file mode 100644
index 0000000..48dacff
--- /dev/null
+++ b/Additional/rearange.cpp
@@ -0,0 +1,55 @@
+#include<iostream>
+#include"../Seminar04/linked-list-utils.h"
+
+using ListNode = LinkedListNode<int>;
+
+ListNode* rearange(ListNode* head) {
+    ListNode* oddStart = nullptr;
+    ListNode* oddIter = nullptr;
+
+    ListNode* evenStart = nullptr;
+    ListNode* evenIter = nullptr;
+
+    while(head != nullptr) {
+        if(head->data % 2 == 1) {
+            if(oddIter == nullptr) {
+                oddStart = head;
+                oddIter = head;
+            }
+            else {
+                oddIter->next = head;
+                oddIter = oddIter->next;
+            }
+        }
+        else {
+            if(evenIter == nullptr) {
+                evenStart = head;
+                evenIter = head;
+            }
+            else {
+                evenIter->next = head;
+                evenIter = evenIter->next;
+            }
+        }
+
+        head = head->next;
+    }
+
+    if(evenStart == nullptr)
+        return oddStart;
+
+    evenIter->next = oddStart;
+    
+    if(oddIter != nullptr)
+        oddIter->next = nullptr;
+    
+    return evenStart;
+}
+
+int main() {
+    ListNode* ll = new ListNode(3, new ListNode(5, new ListNode(2, new ListNode(9, new ListNode(4)))));
+    ListNode* res = rearange(ll);
+
+    printLinkedList(res);
+    freeList(res);
+}
\ No newline at end of file
diff --git a/Additional/reverse-nodes-in-k-group.cpp b/Additional/reverse-nodes-in-k-group.cpp
new file mode 100644
index 0000000..70b63fd
--- /dev/null
+++ b/Additional/reverse-nodes-in-k-group.cpp
@@ -0,0 +1,54 @@
+#include<iostream>
+#include"../Seminar04/linked-list-utils.h"
+
+using ListNode = LinkedListNode<int>;
+
+ListNode* getNext(ListNode* head, int k) {
+    while(k && head) {
+        head = head->next;
+        --k;
+    }
+
+    return head;
+}
+
+ListNode* reverse(ListNode*& head) {
+    ListNode* next = nullptr;
+    ListNode* prev = nullptr;
+    ListNode* it = head;
+    ListNode* tmp = head;
+
+    while(it) {
+        next = it->next;
+        it->next = prev;
+        prev = it;
+        it = next;
+    }
+
+    head = prev;
+    return tmp;
+}
+
+ListNode* reverseKGroup(ListNode* head, int k) {
+    ListNode* end = getNext(head, k - 1);
+
+    if(end == nullptr)
+        return head;
+
+    ListNode* next = end->next;
+
+    end->next = nullptr;
+    
+    ListNode* last = reverse(head);
+    ListNode* res = reverseKGroup(next, k);
+
+    last->next = res;
+    return head;
+}
+
+int main() {
+    ListNode* ll = fromList({1, 2, 3, 4, 5, 6, 7,8 ,9,10, 11, 12, 13, 14, 15, 16, 17});
+    ll = reverseKGroup(ll, 4);
+    printLinkedList(ll);
+    freeList(ll);
+}
\ No newline at end of file
diff --git a/Seminar05/LinkedList.hpp b/Seminar05/LinkedList.hpp
index 58f8794..610d999 100644
--- a/Seminar05/LinkedList.hpp
+++ b/Seminar05/LinkedList.hpp
@@ -105,11 +105,11 @@ public:
     }
 
     ConstIterator begin() const {
-        return Iterator(head);
+        return ConstIterator(head);
     }
 
     ConstIterator end() const {
-        return Iterator(nullptr);
+        return ConstIterator(nullptr);
     }
 
     ConstIterator cbegin() const {