Алгоритмы с нуля
Списки, стеки, очереди: чтение кода
Суть Читай реальные сниппеты на JavaScript — баг pointer в развороте, баг удаления по значению, сломанную array queue и паттерн monotonic stack — и выбирай самый рычажный диагноз или фикс.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеБаги pointer в коде linked list не падают громко — они тихо портят структуру. Читай каждый сниппет, прокрути pointer в голове и выбери, что senior-инженер пометит первым.
Цель
Потренируй цикл, который ты гоняешь на каждом разборе списков/стеков/очередей: читай движения pointer, предскажи, где теряется узел или где неверно заявлена сложность, и назови точный фикс.
Сниппет 1 — разворот, теряющий хвост
function reverse(head) {
let prev = null;
let current = head;
while (current !== null) {
current.next = prev; // развернуть pointer
prev = current;
current = current.next; // продвинуться
}
return prev;
} Викторина
Completed
Что произойдёт при запуске на [10] -> [20] -> [30]?
Heads-up Не может: строка current = current.next читает только что перезаписанный pointer. На узле 10 current.next теперь null (prev), поэтому цикл завершается после одного узла, а 20, 30 теряются.
Heads-up Первый pointer мутирован (10.next становится null), так что список уже испорчен, а не без изменений. Обход также завершается рано, потому что продвижение читает перезаписанный pointer.
Heads-up Исключение не бросается — current чисто становится null и цикл просто выходит рано. Баг — тихое усечение, что хуже падения.
Сниппет 2 — удаление по значению без sentinel
function deleteValue(head, target) {
let current = head;
while (current !== null) {
if (current.value === target) {
current = current.next; // "удалить" его
}
current = current.next;
}
return head;
} Викторина
Completed
Удаляет ли это целевой узел из списка?
Heads-up current — локальная переменная. Её перемещение не меняет pointer списка. Чтобы отвязать узел, надо изменить поле next предыдущего узла, а не локальную копию ссылки.
Heads-up Он не удаляет ничего нигде — ни голову, ни середину. Ни один pointer предшественника никогда не переписывается, поэтому ни один узел не отвязывается ни в одной позиции.
Heads-up Ничего не удаляется, значит утекать нечему. Фикс — отслеживать prev и ставить prev.next = current.next; sentinel-голова убирает спецслучай головы.
Сниппет 3 — array queue под нагрузкой
class Queue {
constructor() { this.items = []; }
enqueue(x) { this.items.push(x); }
dequeue() { return this.items.shift(); }
}
// Драйвер: поток из 1 000 000 пар enqueue/dequeue Викторина
Completed
Очередь корректна, но нагрузочный тест показывает, что она еле ползёт. В чём причина и самый рычажный фикс?
Heads-up push амортизированно O(1) и в порядке. unshift — O(n) как и shift, и сделал бы медленным ещё и enqueue. Дефект — shift на dequeue, а не push.
Heads-up Ёмкость не чинит стоимость переиндексации на каждый dequeue. Даже огромный массив платит O(n) на каждый shift. Надо перестать переиндексировать — использовать pointer/индексы.
Heads-up Можно — circular buffer над массивом с индексами front/rear — отличная queue за O(1). Проблема именно в вызове shift, а не в массиве.
Сниппет 4 — паттерн monotonic stack
function dailyWarmerWait(temps) {
const result = new Array(temps.length).fill(0);
const stack = []; // индексы, убывающие температуры
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const j = stack.pop();
result[j] = i - j; // дней до более тёплой температуры
}
stack.push(i);
}
return result;
} Викторина
Completed
Для temps [73, 74, 75, 71, 69, 72, 76, 73] что это возвращает и какова сложность?
Heads-up Он записывает разрыв в днях (i - j), а не значение температуры. Паттерн — next-greater по расстоянию, а не по значению; прочитай, что пишется в result[j].
Heads-up Вложенный while не делает его квадратичным. Каждый индекс попается максимум один раз за весь прогон, так что суммарные попы ограничены n: алгоритм O(n) амортизированно.
Heads-up 0 корректен ровно для индексов, которые никогда не попаются — дней без более тёплого будущего дня (здесь последние 76 и 73). Каждому попнутому индексу пишется его реальный разрыв.
Итог
Каждый баг списков/стеков/очередей читается в pointer и cost model. Разворот должен сохранить преемника до перезаписи current.next, иначе теряет хвост. Удаление должно переставить предшественника — перемещение локальной ссылки не меняет ничего — а sentinel-голова стирает спецслучай головы. FIFO queue никогда не делает dequeue через shift; используй pointer head/tail или circular buffer для O(1). А monotonic stack остаётся линейным, потому что каждый индекс пушится один раз и попается максимум один раз, независимо от внутреннего while.