Merge branch 'main' of https://github.com/stoychoX/Data-structures-and-algorithms

8 files changed, 205 insertions, 0 deletions

diff --git a/Practicum/pract05/readme.md b/Practicum/pract05/readme.md
new file mode 100644
index 0000000..e335dcd
--- /dev/null
+++ b/Practicum/pract05/readme.md
@@ -0,0 +1,10 @@
+# Практикум №5 по Структури от данни, спец. ИС
+
+## Основни задачи за свързани списъци, които ще решим заедно:
+- [**Reverse a linked list**](https://www.hackerrank.com/challenges/reverse-a-linked-list/problem)
+- [**Middle of linked list**](https://leetcode.com/problems/middle-of-the-linked-list/description/)
+- [**Cycle Detection**](https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem)
+- [**Intersection of two linked lists**](https://leetcode.com/problems/intersection-of-two-linked-lists/description/)
+
+---
+[**Линк към задачите**](https://leetcode.com/problem-list/anqpylct/)
diff --git a/Practicum/pract05/solutions/Task01.cpp b/Practicum/pract05/solutions/Task01.cpp
new file mode 100644
index 0000000..1f9e7a9
--- /dev/null
+++ b/Practicum/pract05/solutions/Task01.cpp
@@ -0,0 +1,17 @@
+SinglyLinkedListNode* reverse(SinglyLinkedListNode* llist) {
+    if(!llist)
+        return nullptr;
+        
+    SinglyLinkedListNode* curr = llist;
+    SinglyLinkedListNode* prev = nullptr;
+    
+    while(curr)
+    {
+        SinglyLinkedListNode* next = curr->next;
+        curr->next = prev;
+        prev = curr;
+        curr = next;
+    }
+    
+    return prev;
+}
diff --git a/Practicum/pract05/solutions/Task02.cpp b/Practicum/pract05/solutions/Task02.cpp
new file mode 100644
index 0000000..4905d58
--- /dev/null
+++ b/Practicum/pract05/solutions/Task02.cpp
@@ -0,0 +1,16 @@
+class Solution {
+public:
+    ListNode* middleNode(ListNode* head) {
+        if(!head)
+            return nullptr;
+      
+        ListNode* middle = head;
+        ListNode* end = head;
+
+        while(end != nullptr && end->next != nullptr) {
+            middle = middle->next;
+            end = end->next->next;
+        }
+        return middle;        
+    }
+};
diff --git a/Practicum/pract05/solutions/Task03.cpp b/Practicum/pract05/solutions/Task03.cpp
new file mode 100644
index 0000000..42282c6
--- /dev/null
+++ b/Practicum/pract05/solutions/Task03.cpp
@@ -0,0 +1,18 @@
+bool has_cycle(SinglyLinkedListNode* head) {
+    if(!head)
+        return false;
+        
+    SinglyLinkedListNode* slow = head;
+    SinglyLinkedListNode* fast = head;
+    
+    while(fast && fast->next)
+    {
+        slow = slow->next;
+        fast = fast->next->next;
+        
+        if(slow == fast)
+            return true;
+    }
+    
+    return false;
+}
diff --git a/Practicum/pract05/solutions/Task04.cpp b/Practicum/pract05/solutions/Task04.cpp
new file mode 100644
index 0000000..3fc11a5
--- /dev/null
+++ b/Practicum/pract05/solutions/Task04.cpp
@@ -0,0 +1,52 @@
+/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ *     int val;
+ *     ListNode *next;
+ *     ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+class Solution {
+public:
+    size_t getLen(ListNode* head)
+    {
+        size_t cnt = 0;
+        while(head)
+        {
+            head = head->next;
+            cnt++;
+        }
+
+        return cnt;
+    }
+    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
+        if(!headA || !headB)
+            return nullptr;
+
+        size_t sizeA = getLen(headA);
+        size_t sizeB = getLen(headB);
+
+        while(sizeA > sizeB)
+        {
+            headA = headA->next;
+            sizeA--;
+        }
+
+        while(sizeB > sizeA)
+        {
+            headB = headB->next;
+            sizeB--;
+        }
+
+        while(headA && headB)
+        {
+            if(headA == headB)
+                return headA;
+
+            headA = headA->next;
+            headB = headB->next;
+        }
+        
+        return nullptr;
+    }
+};
diff --git a/Practicum/pract06/readme.md b/Practicum/pract06/readme.md
new file mode 100644
index 0000000..087c6d3
--- /dev/null
+++ b/Practicum/pract06/readme.md
@@ -0,0 +1,11 @@
+# Практикум №5 по Структури от данни, спец. ИС

+

+---

+

+[**Next Greatest Element**](https://leetcode.com/problems/next-greater-element-ii/description/)

+

+[**Asteroid Collision**](https://leetcode.com/problems/asteroid-collision/description/)

+

+---

+

+[**Линк към задачите**](https://leetcode.com/problem-list/awthx4gv/)

diff --git a/Practicum/pract06/solutions/Task 01.cpp b/Practicum/pract06/solutions/Task 01.cpp
new file mode 100644
index 0000000..9ddd5e8
--- /dev/null
+++ b/Practicum/pract06/solutions/Task 01.cpp
@@ -0,0 +1,33 @@
+#include <vector>

+#include <stack>

+

+class Solution

+{

+public:

+    std::vector<int> nextGreaterElements(std::vector<int> &nums)

+    {

+        std::stack<std::pair<int, int>> stack;

+        std::vector<int> ans(nums.size(), -1);

+        for (int i = 0; i < nums.size(); ++i)

+        {

+            while (!stack.empty() && stack.top().first < nums[i])

+            {

+                ans[stack.top().second] = nums[i];

+                stack.pop();

+            }

+

+            stack.emplace(nums[i], i);

+        }

+

+        for (int i = 0; i < nums.size(); ++i)

+        {

+            while (!stack.empty() && stack.top().first < nums[i])

+            {

+                ans[stack.top().second] = nums[i];

+                stack.pop();

+            }

+        }

+

+        return ans;

+    }

+};

diff --git a/Practicum/pract06/solutions/Task 02.cpp b/Practicum/pract06/solutions/Task 02.cpp
new file mode 100644
index 0000000..6009d36
--- /dev/null
+++ b/Practicum/pract06/solutions/Task 02.cpp
@@ -0,0 +1,48 @@
+#include <string>

+#include <stack>

+#include <vector>

+

+class Solution

+{

+public:

+    std::vector<int> asteroidCollision(std::vector<int> &asteroids)

+    {

+        std::stack<int> stack;

+

+        for (int i = 0; i < asteroids.size(); ++i)

+        {

+            if (asteroids[i] > 0 || (stack.size() && stack.top() < 0))

+            {

+                stack.push(asteroids[i]);

+                continue;

+            }

+

+            bool addNeg = true;

+            while (stack.size() && stack.top() > 0 && stack.top() + asteroids[i] <= 0)

+            {

+                if (stack.top() + asteroids[i] == 0)

+                {

+                    stack.pop();

+                    addNeg = false;

+                    break;

+                }

+                stack.pop();

+            }

+

+            if (addNeg && (stack.empty() || stack.top() < 0))

+            {

+                stack.push(asteroids[i]);

+            }

+        }

+

+        int idx = stack.size();

+        std::vector<int> result(idx);

+        while (stack.size())

+        {

+            result[--idx] = stack.top();

+            stack.pop();

+        }

+

+        return result;

+    }

+};
\ No newline at end of file