Удалить узел из n-го последнего положения в связанном списке


Описание:

Дан связный список, удалить в N- й узел из конца списка и возвращает его голову.

Данный связанный список: 1->2->3->4->5, и N = 2.

После удаления второй узел из конца связанного списка будет 1->2->3->5.

Примечание:

Дано число n всегда будет действителен. Попробуйте сделать это в один проход.

Код:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int total = 0;
        ListNode current = head;
        while (current != null) {
            total++;
            current = current.next;
        }
        // current must be null here

        // 1 based index
        int indexToRemove = total - n + 1;
        if (indexToRemove < 0) {
            return null;
        }
        if (1 == total && n == 1) {
            return null;
        }
        if (indexToRemove == 1) {
            return head.next;
        }

        current = head;
        ListNode prev = null;
        for (int i = 0; i < indexToRemove - 1; i++) {
            prev = current;
            current = current.next;
        }
        // i > indexToRemove

        if (current == null) { // last
            prev.next = null;
        }
        else {
            prev.next = current.next;   
        }
        return head;
    }
}

Вопросы:

Мне удалось запустить код и пройти все испытания, но я все еще чувствую себя в замешательстве при работе с off-by-one errors и NullPointerException. На вопрос, почувствовал, сначала совсем легко, но реализация заняла много времени из-за двух вышеуказанных ошибок и исправлять их, это было похоже на стрельбу в темноте.

Я все еще чувствую, я написал много лишнего кода, который можно было бы избежать.

Какая ментальная модель или основные правила я могу научиться визуализировать и понимать состояния программы и избежать таких ошибок?



Комментарии
3 ответа

Вам не удалось решить "попробовать сделать это в один проход", то, как вы итерации через список, чтобы найти общий размер и второй раз, чтобы найти n-й элемент с самого начала.

Алгоритмическая идея состоит в том, чтобы использовать два указателя в списке:


  • Инициализировать poiner1 в голову, заранее в N раз (если N-это расстояние от хвост искать)

  • Затем, инициализации pointer2 на голову, заранее как указатели, пока pointer1 нуль, т. е. достигнут конец списка.

  • Теперь, pointer2 должен указывать на конец n-го элемента

Удаление как обычно.

3
ответ дан 9 апреля 2018 в 06:04 Источник Поделиться

Я буду строить свой ответ следующим образом:


  • Общие (Ява) что доставит некоторое неудобство

  • Прямые высказывания о вашей реализации

  • Улучшения

  • Как это может выглядеть

Вообще что доставит некоторое неудобство:


  • Первое, что вы должны сделать, это проверить ваши доводы за любой неверный ввод. Что, если head==null? Что, если n<0? Сделать предположения о ваших рассуждениях явные и получить, что из пути сразу, так будет легче думать об остальных, потому что эти крайние случаи исключены.

  • Сделать метод статическим, если нет экземпляра (нестатическим) полям, которые вы используете.

  • Есть несколько вещей, которые могли бы быть извлечены в специальных методов, которые могли бы улучшить читаемость и делают его возможным для повторного использования. Кандидатов: получение длины связного списка и удаления некоторых элементов в связанном списке по индексу.

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

Замечания по реализации:

Смею предположить, что n быть действительным означает 1 < n <= total+1 и что head!=null.
Если head==null или недействительным n все ломается.
Я дам мое выступление будет за кусок кода кусок


  • Найти длину связного списка.

  • Используйте предыдущие длина перевернуть n чтобы получить индекс, по-прежнему с
    1-индексации с фронта.

  • вы создаете три ветви и вернуться пораньше. Второй избыточен, потому что n==1&&total==1 => indexToRemove==1 && head!=null && head.next==null.

  • Не indexToRemove 1-индексированные? Не означает ли это, по крайней мере 1?
    Вы защищаете от недопустимых n здесь? Вы только защитить от
    n>total+1.

  • вы ходите по списку, пока не дойдете до узла, который должен быть удален,
    вспоминая предыдущий узел, потому что вы должны изменить указатель
    есть.

  • Пока n>=0 вы гарантированно, что вы не
    есть NPE с current.nextпотому что первого контура.
    Это не очень понятно, хотя, потому что вы посчитайте длину в первую петлю, а затем сделать некоторые арифметические операции над этой длины и некоторого аргумента и затем попробуйте снова перебирать список с результатами. Некоторые лучшие способы сделать это ясно при расчете indexToReturn путем добавления max(.., total+1) или использовать total в цикле второй раз и перерыв, когда вы находитесь в правильном узле.

  • После второго цикла i>indexToRemove -1 таким образом, поскольку инкремент на 1 у нас есть i==indexToRemove. То, что вы написали в комментарии-это неправильно. Это делает первый, если заблокировать ненужного и мертвого кода.

  • Сейчас вы находитесь на узел, который вы хотите удалить, так что вы установите указатель на предыдущий узел на нуль, и вы сделали.

Улучшения:

Все, что я сказал под общим что доставит некоторое неудобство.

Изменение противоестественным 1-индексации на общих 0-индексации. Это улучшит читаемость и снизит вероятность от одной ошибки.

Как я хотел бы сделать это:

Я решил проверить n это слишком большой, в обоих методах, потому что мне нравятся самодостаточные методы. В принципе я мог удалить его из removeItemFromEnd и удалить вызов size для того чтобы сохранить время. Это не поможет сложность времени, и это делает методы более вкупе, так что здесь я выбираю структуры над скоростью.

class Solution {
public int size(ListNode head) {
int total = 0;
ListNode current = head;
while (current != null) {
total++;
}
return total;
}

public removeItem(ListNode head, int index) {
if (index < 0) {
throw new IndexOutOfBoundsException("Index " + index + " is too small.");
}
if (head == null) {
return null;
}

if (index == 0){
return head.next;
}

ListNode current = head;
ListNode prev = null;
for (int i = 0; i < index && current != null; i++) {
prev = current;
current = current.next;
}

if (current == null) {
throw new IndexOutOfBoundsException("Index " + index + " is too big.");
}
prev.next = current.next;
return head;
}

public ListNode removeItemFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}

if (n<1) {
throw new IndexOutOfBoundsException("Index " + n + " is too small.");
}

int size = size(head);
if (n > size){
throw new IndexOutOfBoundsException("Index " + n " is too big.");
}

return removeItem(head, size - n); // size - n is zero indexed
}
}

1
ответ дан 7 апреля 2018 в 10:04 Источник Поделиться

Часть ниже мне кажется излишним и неправильным:

    if (indexToRemove < 0) {
return null;
}

Если я понял правильно, вы говорите n это всегда действует. На примере, я понимаю, что это означает n не менее 1 и не более чем список длины. Отсюда indexToRemove не может быть отрицательным и все if() является ничтожным.

В любом случае, даже если вы считать недействительным nнельзя удалить несуществующий элемент, но во главе списка остается в таком случае, я бы ожидать return head; здесь. Однако, то условие должно быть indexToRemove <= 0.

Также на следующий условное ветвление-это лишнее:

    if (1 == total && n == 1) {
return null;
}

потому что случай совершенно обрабатываются оператором, следующим его:

    if (indexToRemove == 1) {
return head.next;
}

Комментарий вы оставили после последней петли, кажется, сообщают:

    for (int i = 0; i < indexToRemove - 1; i++) {
prev = current;
current = current.next;
}
// i > indexToRemove

Петли петли, пока условие i < indexToRemove - 1 доволен.
Как i растет по одной на каждой итерации, условие будет нарушено, когда i становится равной indexToRemove - 1следовательно, он является менее indexToRemove, противоположное тому, что говорится в комментариях!

Наконец, эта часть тоже бесполезно:

    if (current == null) { // last
prev.next = null;
}
else { ... }

Если n == 1 вы действительно хотите удалить последний элемент из списка.
На самом деле, indexToRemove имеет значение total - n + 1 какие результаты в total, т. е. индекс последнего элемента.

Тем не менее, инвариант цикла-это:


заранее: current это (i+1)-ой пункт
пост: current это (i+2)-ой пункт

(Проверьте: на въезд, i == 0 и current == head.)

Поэтому, когда цикл завершается в i = indexToRemove - 1 после i++последнее значение i обработан был indexToRemove - 2и current был пункт в положении i+2т. е. indexToRemove. В результате он не может быть null!

Все, что вам нужно сделать после цикла:

    prev.next = current.next;   
return head;

current.next будучи null МФЛ n==1).

0
ответ дан 7 апреля 2018 в 08:04 Источник Поделиться