Сдвинуть все нулевые элементы в конец списка

Условие

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

Ввод: [1, 0, 8, 9]

Вывод: [1, 8, 9, 0]

Ответ

Пройдите список двумя указателями: перепишите ненулевые значения в начало в прежнем порядке, затем заполните оставшиеся позиции нулями. Время O(n), дополнительная память O(1).

Реализация меняет список на месте:

def move_zeros(values):
    write = 0
    for read in range(len(values)):
        if values[read] != 0:
            values[write] = values[read]
            write += 1
    for index in range(write, len(values)):
        values[index] = 0
    return values

Для [1, 0, 8, 9] результат [1, 8, 9, 0]. Указатель записи не обгоняет чтение, поэтому непрочитанные элементы не повреждаются. Порядок ненулевых чисел сохраняется; пустой список обрабатывается без отдельной ветки.