Связные списки

Linked lists меняют direct indexing на дешевую перестановку pointers, когда нужный node уже найден. На интервью обычно проверяют аккуратный traversal: reverse list, detect cycle, merge sorted lists или remove node с tracking previous pointer.

Компромисс: сравните время, память и сложность реализации до выбора структуры или паттерна.

На интервью: Сильный ответ рисует nodes, называет current и previous pointers и объясняет, когда dummy head убирает edge cases вокруг первого node.

Типовые ошибки: Стоимость поиска все еще O(n). Обновление next pointers в неправильном порядке может потерять остаток list. Всегда проверяйте empty, single-node и head-removal cases.

Чеклист:

• Отслеживайте previous, current и next.
• Рассмотрите dummy head.
• Не теряйте references.
• Обрабатывайте cycles явно.