Как удалить N-й узел из конца списка — Blind 75 LeetCode Question

Описание задачи:

Учитывая head связанного списка, удалите n-й узел из конца списка и верните его заголовок. п

Пример 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Пример 2:

Input: head = [1], n = 1
Output: []

Пример 3:

Input: head = [1,2], n = 1
Output: [1]

Ограничения:

• Количество узлов в списке равно sz.
• 1 <= размер <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Обоснование:

Давайте попробуем сделать что-нибудь естественное. Чтобы удалить N-й узел с конца, важно сначала определить общее количество узлов в списке. Подсчитав количество узлов, становится просто определить индекс узла, который необходимо удалить. Здесь возможны два сценария. Первый и самый простой сценарий — удаление некраевого узла. В этом случае все, что нам нужно сделать, это изменить указатель предыдущего узла (next) на узел после удаленного.

Давайте рассмотрим пример: Список → [1,2,3,4,5] , n=2.

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

Оценим сложность этого подхода. Мы выполняем два полных обхода списка, поэтому временная сложность составляет O(2 * N), а поскольку мы сохраняем только размер списка, объемная сложность составляет O(1).

Код:

public ListNode removeNthFromEnd(ListNode head, int n) {
        int size = 0;
        ListNode tmp = head;
        while (tmp != null) { 
            size++;
            tmp = tmp.next;
        }
        int prevIndex = size - n;
        if (prevIndex == 0) return head.next;

        tmp = head;
        while (prevIndex != 1) {
            tmp = tmp.next;
            prevIndex--;
        }
        tmp.next = tmp.next.next;
        return head;
    }

Как оптимизировать это решение?

Внимательно изучив условия, мы видим, что число удаляемых узлов определяется таким значением, что 1 <= n <= sz, где sz< /strong> — размер списка. Решение включает использование двух указателей. Мы создаем быстрый указатель, указывающий на N-й узел, и медленный указатель, указывающий на начало списка.

Далее мы повторяем до тех пор, пока быстрый указатель не достигнет конца списка. Медленный указатель отстает от быстрого указателя на n, поэтому теперь он указывает на узел, предшествующий тому, который мы хотим удалить.

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

Код:

public ListNode removeNthFromEnd(ListNode head, int n) {
  int delay = n;
  ListNode fast = head;
  while(delay > 0) {
    delay--;
    fast = fast.next;
  }
  if (fast == null) return head.next; // point

  ListNode prev = head;
  while (tmp.next != null) {
    tmp = tmp.next;
    prev = prev.next;
  }

  prev.next = prev.next.next;
  return head;
}

Я хотел бы подчеркнуть несколько важных моментов в этом коде. Мы должны помнить сценарий, в котором необходимо удалить первый узел. В этом сценарии быстрый указатель будет нулевым, и мы должны вернуть второй узел в качестве нового заголовка списка. Как видим, мы успешно нашли и удалили узел всего за один проход по списку.

Сложность:

1. Временная сложность: O(N)
2. Пространственная сложность: O(1)

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

До скорой встречи! ✌