Задача 02 — связный список (C++)

Глава I. Общая информация

Цель: развернуть список, найти середину и определить цикл — без единой дополнительной аллокации, только перелинковка указателей.
Почему это в Eltex: списки соединений, очереди задач, таблицы состояний — везде связные структуры. Приём двух указателей (slow/fast), которым решаются find_middle и has_cycle, — это алгоритм Флойда, тот же паттерн всплывает при поиске циклов в графах зависимостей и в обходе кольцевых структур.
Что сдаётся: solution.cpp, проходящий python3 grade.py 02.

Глава II. Что нужно знать до старта

Даны функции над односвязным списком Node{int value; Node* next;}:

Node* reverse_list(Node* head);   // развернуть список на месте, вернуть новую голову
Node* find_middle(Node* head);    // середина; для чётной длины — второй из двух средних
bool  has_cycle(Node* head);      // есть ли цикл

Механизм двух указателей: slow идёт на 1 узел за шаг, fast — на 2. Для find_middle, когда fast доходит до конца (fast == nullptr или fast->next == nullptr), slow стоит ровно в середине — за счёт того, что slow проходит вдвое меньше узлов, чем fast. Для чётной длины условие остановки должно давать именно второй из двух средних узлов — это проверяется на списке длины 2 и 4.

Для has_cycle тот же дуэт указателей ловит цикл иначе: если цикл есть, fast заходит в него и после каждого шага сокращает расстояние до slow внутри цикла на 1 узел (потому что относительная скорость fast к slow внутри цикла — 1 узел/шаг), значит рано или поздно slow == fast; если цикла нет, fast первым дойдёт до nullptr.

reverse_list разворачивается за один проход тремя указателями prev/cur/next: на каждом шаге переставляется cur->next = prev до итерации по цепочке. Рекурсивный разворот сюда не годится — он тратит O(n) памяти стека вызовов и нарушает требование O(1) дополнительной памяти.

Почему дальше: тот же принцип «два индекса вместо лишней памяти» — в задаче 03, только на массиве, а не на указателях.

Глава III. Требования

никаких аллокаций, O(1) дополнительной памяти, один проход там, где это возможно;
find_middle и has_cycle — через два указателя (медленный/быстрый);
корректная работа с пустым списком и списком из одного узла.

Глава IV. Критерии приёмки

Проверка: python3 grade.py 02. Критерий: все ok, ASAN/UBSAN чистые (утечки в тесте считаются ошибкой — тест сам освобождает память).

Глава V. Ловушки

Забыть проверку head == nullptr в начале любой из трёх функций → разыменование нулевого указателя → падение/ASAN SEGV на пустом списке.
В find_middle неверное условие остановки цикла (fast->next без проверки самого fast на nullptr) → на списке чётной длины либо возвращается не тот из двух средних узлов, либо падение на последнем шаге.
В reverse_list переставить cur->next = prev до сохранения старого cur->next во временную переменную → потеря хвоста списка, обход обрывается раньше конца.
Рекурсивный reverse_list вместо итеративного → лишняя память стека на каждый вызов → нарушение требования O(1), на длинном списке возможен stack overflow.

Факты для карточек

base | Во сколько раз быстрее идёт fast относительно slow в паре двух указателей? — в 2 раза
core | Почему рекурсивный разворот списка не годится под требование O(1) памяти? — каждый вызов кладёт кадр в стек, суммарно O(n) памяти
core | На чём основано доказательство, что fast догонит slow при цикле? — внутри цикла расстояние между ними сокращается на 1 узел за шаг
base | Сколько дополнительных указателей нужно для итеративного разворота списка? — 3 (prev, cur, next)

После сдачи

Разбор: почему алгоритм Флойда работает за O(n) времени и O(1) памяти в обоих режимах (поиск середины и поиск цикла), и как тот же приём переносится на поиск цикла в графе.

6.2 KiB Raw Permalink Blame History Unescape Escape