[SDP/S04] Solved exercises from seminar 4

2 files changed, 225 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/exercises.cpp b/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/exercises.cpp
new file mode 100644
index 0000000..5fa8359
--- /dev/null
+++ b/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/exercises.cpp
@@ -0,0 +1,145 @@
+#include "linked-list-utils.h"
+#define LLN LinkedListNode
+#include <deque>
+
+// Ex1
+
+template <class T>
+void insertBeg(LLN<T>*& head, const T& elem) {
+	head = new LLN<int>(elem, head);
+}
+
+void ex1() {
+	LLN<int>* head = new LLN<int>(2, new LLN<int>(3, new LLN<int>(4)));
+	printLinkedList(head);
+
+	insertBeg(head, 1);
+	printLinkedList(head);
+
+	freeList(head);
+}
+
+// Ex 2
+
+template <class T>
+void reverse(LLN<T>*& head) {
+	LLN<T>* newHead = nullptr;
+	LLN<T>* iter;
+	while (head != nullptr) {
+		iter = head->next;
+		head->next = newHead;
+		newHead = head;
+		head = iter;
+	}
+	head = newHead;
+}
+
+void ex2() {
+	LLN<int>* head = new LLN<int>(1, new LLN<int>(2, new LLN<int>(3, new LLN<int>(4, new LLN<int>(5)))));
+	printLinkedList(head);
+
+	reverse(head);
+	printLinkedList(head);
+
+	freeList(head);
+}
+
+// Ex 3
+
+template <class T>
+LLN<T>* inefficientMiddle(LLN<T>* head) {
+	std::deque<LLN<T>*> ptrs;
+	while (head != nullptr) {
+		ptrs.push_back(head);
+		head = head->next;
+	}
+	while (ptrs.size() > 2) {
+		ptrs.pop_front();
+		ptrs.pop_back();
+	}
+	return ptrs.front();
+}
+
+template <class T>
+LLN<T>* middle(LLN<T>* head) {
+	LLN<T>* fast = head, *slow = head;
+	while (fast && fast->next) {
+		fast = fast->next->next;
+		slow = slow->next;
+	}
+	return slow;
+}
+
+void ex3() {
+	LLN<int>* head1 = new LLN<int>(1, new LLN<int>(2, new LLN<int>(3, new LLN<int>(4, new LLN<int>(5)))));
+	printLinkedList(head1);
+	LLN<int>* head2 = new LLN<int>(1, new LLN<int>(2, new LLN<int>(3, new LLN<int>(4))));
+	printLinkedList(head2);
+
+	std::cout << middle(head1)->data << std::endl;
+	std::cout << middle(head2)->data << std::endl;
+
+	freeList(head1);
+	freeList(head2);
+}
+
+// Ex4
+
+template <class T>
+void reorder(LLN<T>*& head) {
+	if (!head) return;
+
+	LLN<T>* iter = head, *plast = head, *tail = head;
+	while (iter->next != nullptr && iter->next->next != nullptr) {
+		plast = iter;
+		iter = iter->next;
+		while (plast->next->next != nullptr)
+			plast = plast->next;
+		tail->next = plast->next;
+		tail->next->next = iter;
+		tail = tail->next->next;
+		plast->next = nullptr;
+	}
+}
+
+void ex4() {
+	LLN<int>* head = new LLN<int>(1, new LLN<int>(2, new LLN<int>(3, new LLN<int>(4, new LLN<int>(5)))));
+	printLinkedList(head);
+
+	reorder(head);
+	printLinkedList(head);
+
+	freeList(head);
+
+
+	head = new LLN<int>(1, new LLN<int>(2, new LLN<int>(3, new LLN<int>(4, new LLN<int>(5, new LLN<int>(6))))));
+	printLinkedList(head);
+
+	reorder(head);
+	printLinkedList(head);
+
+	freeList(head);
+
+
+	head = new LLN<int>(1);
+	printLinkedList(head);
+
+	reorder(head);
+	printLinkedList(head);
+
+	freeList(head);
+
+
+	head = nullptr;
+	printLinkedList(head);
+
+	reorder(head);
+	printLinkedList(head);
+
+	freeList(head);
+}
+
+
+int main() {
+	ex4();
+}
diff --git a/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/linked-list-utils.h b/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/linked-list-utils.h
new file mode 100644
index 0000000..013876c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/04-Seminar-26.10.2022/linked-list-utils.h
@@ -0,0 +1,80 @@
+/* Author  : StoychoX
+ * Source  : https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar04/linked-list-utils.h
+ * License : <none>
+ * Date    : 22.11.2022
+ */
+
+#include<iostream>
+#include<initializer_list>
+
+template<class T>
+struct LinkedListNode {
+    T data;
+    LinkedListNode<T>* next;
+
+    LinkedListNode(const T& elem, LinkedListNode<T>* n = nullptr) : data{elem}, next {n} {} 
+};
+
+template<class T>
+void printLinkedList(const LinkedListNode<T>* ll) {
+    const LinkedListNode<T>* iterate = ll;
+
+    while(iterate) {
+        std::cout << iterate->data << " ";
+        iterate = iterate->next;
+    }
+
+    std::cout << std::endl;
+}
+
+template<class T>
+void printLinkedList(const LinkedListNode<T>* ll, void (*print)(T)) {
+    const LinkedListNode<T>* iterate = ll;
+
+    while(iterate) {
+        print(iterate->data);
+        iterate = iterate->next;
+    }
+
+    std::cout << std::endl;
+}
+
+template<class T>
+void printLinkedList(const LinkedListNode<T>* ll, void (*print)(const T&)) {
+    const LinkedListNode<T>* iterate = ll;
+
+    while(iterate) {
+        print(iterate->data);
+        iterate = iterate->next;
+    }
+
+    std::cout << std::endl;
+}
+
+template<class T>
+LinkedListNode<T>* fromList(const std::initializer_list<T>& l) {
+    LinkedListNode<T>* toReturn = nullptr;
+    LinkedListNode<T>* iter = nullptr;
+
+    for(const auto& elem : l) {
+        LinkedListNode<T>* toInsert = new LinkedListNode<T>(elem);
+        if(iter == nullptr) {
+            toReturn = toInsert;
+            iter = toInsert;
+        }
+        else {
+            iter->next = toInsert;
+            iter = iter->next;
+        }
+    }
+    return toReturn;
+}
+
+template<class T>
+void freeList(LinkedListNode<T>* ll) {
+    while(ll) {
+        LinkedListNode<T>* toDelete = ll;
+        ll = ll->next;
+        delete toDelete;
+    }
+}