Добавил решение 15 задачи в двухсвязных списках

1 files changed, 58 insertions, 0 deletions

diff --git a/list/task15.cpp b/list/task15.cpp
new file mode 100644
index 0000000..46eb319
--- /dev/null
+++ b/list/task15.cpp
@@ -0,0 +1,58 @@
+#include <iostream>
+#include "list.h"
+
+using namespace std;
+
+int solve(list *&h, list *&t, int k)
+{
+    list *cur = h;
+    while (true)
+    {
+        // Пропускаем n - 1 элементов, чтобы удалить n-й.
+        for (int i = 0; i < k - 1; i++)
+            cur = cur->next;
+
+        list *tmp = cur;
+        cur = cur->next;
+        del_node(h, t, tmp);
+
+        // В случае, если удалённым элементом стала голова или хвост,
+        // список закольцуется, а иначе ничего не изменится.
+        t->next = h;
+        h->prev = t;
+
+        // Если после текущего элемента следует он же, то в списке
+        // остался один элемент, который является ответом.
+        if (cur->next == cur) break;
+    }
+    return cur->inf;
+}
+
+int main()
+{
+    int n;
+    cout << "n = ";
+    cin >> n;
+
+    int k;
+    cout << "k = ";
+    cin >> k;
+
+    list *head = NULL;
+    list *tail = NULL;
+    int x;
+    for (int i = 0; i < n; i++)
+    {
+        cin >> x;
+        push(head, tail, x);
+    }
+
+    // Закольцовываем список
+    tail->next = head;
+    head->prev = tail;
+
+    int result = solve(head, tail, k);
+    cout << result << endl;
+
+    return 0;
+}