---

Задание 1.1. Шаблонный двусвязный список
Реализовать template <typename T> class List со стандартным интерфейсом:

    push_front, push_back, pop_front, pop_back, insert(pos, value), erase(pos), clear, size, empty
    Конструктор копирования, оператор присваивания, move-конструктор и move-присваивание
    Итераторы: begin()/end(), прямой обход, operator++, operator--, operator*, сравнение
    Исключения: pop/erase из пустого списка должны кидать std::out_of_range
    Деструктор не должен давать утечек — проверяется

Задание 1.2. Кольцевой двусвязный список
template <typename T> class RingList, где tail->next == head, head->prev == tail. Те же операции плюс:

    Поворот: rotate(k) — за O(min(k, n−k)) переставить начало списка (элемент, на который указывает «голова», сдвигается на k позиций)
    Эффективный find(value), учитывающий кольцевую структуру (поиск в двух направлениях, выбор кратчайшего пути — на оценку «отлично»)

Блок 2. Алгоритмы (каждое 1–2 балла)
Задание 2.1. Разворот

    reverse() — развернуть список за O(n), без выделения новых узлов (только перекидка указателей). Отдельно — разворот кольцевого списка.

Задание 2.2. Слияние

    merge(other) — слить два отсортированных списка в один, не копируя узлы, а перецепляя их; other после операции пуст. Сложность O(n+m).

Задание 2.3. Сортировка

    sort() для двусвязного списка: merge sort, работающий напрямую с узлами (без массива/вектора). Требование: O(n log n), без рекурсии глубиной n (можно bottom-up или с ограничением). Кольцевой список отсортировать тоже.

Задание 2.4. Удаление дубликатов

    unique() — удалить подряд идущие равные элементы (за O(n))
    removeDuplicates() — удалить ВСЕ дубликаты в неотсортированном списке, минимум два решения: через вспомогательный std::unordered_set (O(n) по времени, O(n) по памяти) и без дополнительной памяти (O(n²))

Задание 2.5. Перестановки узлов

    swapNodes(a, b) — поменять местами два узла по значениям/итераторам, только переставляя указатели, не копируя данные. Отдельный кейс: соседние узлы и крайние (head/tail).
    shift(k) — циклически сдвинуть элементы на k позиций (аналог rotate для обычного списка, узлы не пересоздаются)

Блок 3. Кольцевые списки — специфика (2–3 балла)
Задание 3.1. Проблема Иосифа

    На кольцевом списке из n элементов моделировать отсчёт: удалять каждый k-й элемент, пока не останется один. Вывести порядок удаления. Запрещено моделировать на массиве — только на своём кольцевом списке. Проверить для n=41, k=3 (правильный ответ: последним остаётся элемент с начальной позицией 31).

Задание 3.2. Разделение кольца

    split() — разрезать кольцевой список на два кольца примерно равной длины за один проход, указатель на «середину» без предварительного подсчёта size (алгоритм быстрый/медленный указатель).

Задание 3.3. Проверка кольца

    Функция bool hasCycle(Node* head) по «сырым» указателям на узлы (не ваш класс): детектировать цикл алгоритмом Флойда (черепаха и заяц). Плюс: найти узел, где цикл начинается.