Website Summary Files Commits Branches @commit @diff @stats
path: root / Additional / Additional-2023-SI / MergeIntoList.cpp
diff options
context:
space:
mode:
Commit9eed63a37a808c59990feaaaa3e1725dfdd31f3c (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-10-30 22:33:14 +0200
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2023-10-30 22:33:14 +0200
Filesbc22e2b8407f9207c7a5a8ef999f41446c0cee19 /Additional/Additional-2023-SI/MergeIntoList.cpp
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.tar
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.tar.gz
Data-structures-and-algorithms-9eed63a37a808c59990feaaaa3e1725dfdd31f3c.zip
Parent0f17a224d2934c748b32b908f74724b3299d263a (diff)
Add SI consultation
1 files changed, 117 insertions, 0 deletions
-rw-r--r--Additional/Additional-2023-SI/MergeIntoList.cpp117
diff --git a/Additional/Additional-2023-SI/MergeIntoList.cpp b/Additional/Additional-2023-SI/MergeIntoList.cpp
new file mode 100644
index 0000000..7d575aa
--- /dev/null
+++ b/Additional/Additional-2023-SI/MergeIntoList.cpp
@@ -0,0 +1,117 @@
+#include <iostream>
+
+struct ListNode
+{
+ int val;
+ ListNode *next;
+ ListNode(int x, ListNode *n = nullptr) : val(x), next(n) {}
+};
+
+ListNode *advance(ListNode *from, size_t index)
+{
+ while (index)
+ {
+ if (from == nullptr)
+ {
+ return nullptr;
+ }
+
+ from = from->next;
+ --index;
+ }
+
+ return from;
+}
+
+ListNode *getTail(ListNode *list)
+{
+ if (!list || !list->next)
+ {
+ return list;
+ }
+
+ while (list->next)
+ {
+ list = list->next;
+ }
+ return list;
+}
+
+void freeRagne(ListNode *from, ListNode *to)
+{
+ while (from != to)
+ {
+ ListNode *node = from;
+ from = from->next;
+ delete node;
+ }
+}
+
+void free(ListNode *ll)
+{
+ while (ll)
+ {
+ ListNode *toDelete = ll;
+ ll = ll->next;
+ delete toDelete;
+ }
+}
+
+ListNode *addFront(ListNode *destination, ListNode *target, size_t to)
+{
+ ListNode *tail = getTail(target);
+ ListNode *end = advance(destination, to + 1);
+ tail->next = end;
+ freeRagne(destination, end);
+ return target;
+}
+
+ListNode *mergeInBetween(ListNode *destination, ListNode *target, size_t from, size_t to)
+{
+ if (from == 0)
+ {
+ return addFront(destination, target, to);
+ }
+
+ ListNode *predBegin = advance(destination, from - 1);
+ if (!predBegin)
+ {
+ return nullptr;
+ }
+
+ ListNode *postEnd = advance(predBegin, to - from + 2);
+ ListNode *toDeleteHolder = predBegin->next;
+ ListNode *targetTail = getTail(target);
+
+ predBegin->next = target;
+ targetTail->next = postEnd;
+
+ freeRagne(toDeleteHolder, postEnd);
+
+ return destination;
+}
+
+int main()
+{
+ ListNode *fst = new ListNode(1,
+ new ListNode(2,
+ new ListNode(3,
+ new ListNode(4,
+ new ListNode(6)))));
+
+ ListNode *snd = new ListNode(3,
+ new ListNode(4,
+ new ListNode(5)));
+
+ ListNode *ans = mergeInBetween(fst, snd, 1, 3);
+
+ ListNode *it = ans;
+
+ while(it)
+ {
+ std::cout << it->val << " ";
+ it = it->next;
+ }
+
+ free(ans);
+} \ No newline at end of file