Постоянное пространство, один проход, ежедневная проблема кодирования

Question

Это ежедневная проблема кодирования:

«Учитывая односвязный список и целое число k, удалите последний k-й элемент из списка.k гарантированно будет меньше длины списка.

Список очень длинный, поэтому создание более одного прохода непомерно дорого.

Делайте это в постоянном пространстве и за один проход. ”

...

Вот мое решение:

function removeKthFromEnd() {
    var previous = list.head;
    var kth = list.head;
    var end = list.head;
    for(var i = 0; i < k; i++){
        end = end.next;
    }
    while(end != null) {
        previous = kth;
        end = end.next;
        kth = kth.next;

    }
    previous.next = kth.next;
    kth = null;
}

Я устанавливаю kth, previous и end в начало списка, перебираю k элементов черезсвязанный список, так что пробел между kth и end = k, затем увеличивается kth и предыдущий, ожидая end.next == null, в этот момент kth будет указывать на kth из последнего элемента, а предыдущие - на одну перед ним,Затем просто склейте список обратно, сделав previous.next = kth.next.

Мой вопрос:

Это в постоянном пространстве?Это один проход?

Спасибо.

Answer 1

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