Как работает подход с двумя указателями для перемещения нулей в массиве

Что проверяют

Умеете ли вы решить задачу на месте за один проход и сформулировать инвариант, а не просто вспомнить код. Следом обычно просят сократить число записей или спрашивают, что изменится, если порядок ненулевых элементов неважен.

Как отвечать

Задача: сдвинуть все нули в конец, сохранив порядок остальных, без второго списка.

• указатели: fast идёт по всем элементам, slow показывает, куда ставить следующий ненулевой;
• инвариант: всё левее slow это ненулевые элементы в исходном порядке, между slow и fast лежат только нули. Если сказать это вслух, корректность очевидна;
• шаг: встретили ненулевой, делаем nums[slow], nums[fast] = nums[fast], nums[slow] и сдвигаем slow. Нули сами оказываются справа;
• сложность: O(n) по времени, O(1) по памяти, каждый элемент просматривается один раз.

Второй вариант: сначала переписать ненулевые в начало, потом заполнить хвост нулями от slow до конца. Тоже O(n), но два прохода и лишние записи в хвост, где часть нулей и так стояла. Обмен можно улучшить проверкой if slow != fast, чтобы не менять элемент сам с собой.

В Python функция, которая меняет список на месте, по соглашению возвращает None, как list.sort(). Для обхода удобно for fast, x in enumerate(nums).

Покажите и короткие альтернативы, но с оговорками: nums.sort(key=lambda x: x == 0) работает благодаря стабильности сортировки, но это O(n log n); nums[:] = [x for x in nums if x != 0] + [0] * nums.count(0) линейно, но создаёт новые списки.

Где спотыкаются

Пишут nums = [...] вместо nums[:] = .... Имя внутри функции переназначено, а список у вызывающего кода не изменился.

Удаляют нули через nums.remove(0) и append(0) прямо в цикле по тому же списку. Индексы съезжают, часть нулей пропускается, а каждый remove стоит O(n), итого квадрат.

Берут указатели с двух концов и меняют ноль с последним элементом. Записей меньше, но порядок ненулевых ломается, а это условие задачи. Такой вариант уместен только в версии, где порядок неважен.