Как узнать
связный список, который нужно развернуть (целиком, на отрезке или группами по k), слить, разделить, переставить или очистить от части узлов на месте; или кэш, который переносит элементы в начало, как LRU (хеш-таблица плюс двусвязный список).
Как решать такие задачи
- Нарисуй узлы и стрелки до и после. Назови каждый указатель, который нужно сохранить, чтобы ничего не потерять.
- Прежде чем перезаписать .next, запомни узел, на который он указывает.
- Перецепляй в одном и том же порядке, потом сдвигай каждый указатель на шаг. Проверь первый узел, последний и пустой список.
- Чтобы развернуть только часть (позиции left..right или каждую группу из k), остановись на узле перед ней, разверни её тем же циклом и пришей оба конца обратно.
Вариант: Фиктивная голова
То же, но перед началом списка ставим пустой узел-заглушку. Тогда первый узел ничем не отличается от остальных, и для него не нужен отдельный случай.
- Бери фиктивный узел всякий раз, когда может поменяться сама голова: при слиянии, удалении узлов из начала, делении на части.
- Держи tail на последнем узле ответа и добавляй только после него: tail.next = node, потом tail = tail.next.
- Сдвигай указатель того списка, из которого взял узел. Когда один список кончился, пришей остаток другого за один шаг.
- Верни dummy.next. Чтобы разделить список или выкинуть повторы, собери один или два ответа, каждый со своим фиктивным узлом, и соедини их в конце.
Где встречается
- Ядро Linux. Процессы, открытые файлы и многое другое ядро держит в связных списках (struct list_head). Убрать процесс из очереди — значит перецепить две ссылки, ничего не сдвигая.
- memcached. Записи лежат в двусвязном списке от недавно использованных к давним. Использованную запись перецепляют в начало, а когда память кончается, выкидывают хвост.
- Выделение памяти. malloc в glibc хранит свободные куски памяти в связных списках. Освободить кусок — прицепить его к списку, выделить — отцепить.