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

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

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

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

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

```c
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) памяти в обоих режимах
(поиск середины и поиск цикла), и как тот же приём переносится на поиск цикла в графе.