Удалить N-й узел с конца

Постановка задачи

head = [1, 2, 3, 4, 5]
n = 2

[1, 2, 3, 5]

head = [1]
n = 1

[]

head = [1, 2]
n = 1

[1]

Решение

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

Можно сначала посчитать длину списка, затем удалить узел с позиции length - n. Это решение корректно, но делает два прохода. На интервью обычно хотят увидеть решение за один проход с двумя указателями.

Идея решения:

Создадим фиктивный узел dummy, который указывает на head. Это упростит удаление головы списка.

Дальше используем два указателя: fast и slow. Сначала сдвинем fast на n + 1 шагов от dummy. После этого между fast и slow будет расстояние n + 1 узлов.

Теперь двигаем оба указателя одновременно, пока fast не дойдет до null. В этот момент slow будет стоять прямо перед узлом, который нужно удалить.

Основные шаги:

1. Создаем dummy, где dummy.next = head.
2. Ставим fast и slow на dummy.
3. Сдвигаем fast на n + 1 шагов.
4. Двигаем fast и slow вместе, пока fast не станет null.
5. Удаляем slow.next.
6. Возвращаем dummy.next.

Разберем на примере head = [1, 2, 3, 4, 5], n = 2.

1. Инициализация: slow и fast стоят на dummy.

2. Сдвигаем fast на n + 1 = 3 шага. Теперь между указателями расстояние n + 1.

3. Двигаем slow и fast вместе.

4. Когда fast доходит до null, slow стоит перед удаляемым узлом 4.

5. Удаляем slow.next:

slow.next = slow.next.next

Итог: [1, 2, 3, 5]. Возвращаем dummy.next.

Оценка сложности

Временная сложность

Указатели проходят по списку линейно. Каждый узел посещается не более одного раза, поэтому временная сложность равна O(n).

Пространственная сложность

Мы используем только несколько указателей. Дополнительная память равна O(1).

Код решения

Приведем код решения.

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    fast := dummy
    slow := dummy
 
    for i := 0; i <= n; i++ {
        fast = fast.Next
    }
 
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
 
    slow.Next = slow.Next.Next
    return dummy.Next
}

Итоги

Задача Remove Nth Node From End of List показывает, как расстояние между двумя указателями заменяет предварительный подсчет длины списка.

1. Суть алгоритма: мы держим между fast и slow расстояние n + 1, чтобы к моменту завершения прохода slow стоял перед удаляемым узлом.
2. Эффективность:
   • Временная сложность: O(n), так как мы проходим список один раз.
   • Пространственная сложность: O(1), так как мы используем фиксированное количество указателей.
3. Граничные случаи:
   • Нужно удалить голову: dummy позволяет сделать это без отдельной обработки.
   • В списке один узел: после удаления dummy.next станет null.
   • Нужно удалить последний узел: slow остановится на предпоследнем узле.
4. Оптимальное решение: выполняет один проход и меняет только одну ссылку next, не создавая новый список.