Ежедневный бит (е) C ++ # 105, Распространенная проблема на собеседовании: удаление n-го элемента из конца односвязного списка
Сегодня мы рассмотрим распространенную задачу интервью C++: удаление n-го элемента из конца односвязного списка.
Учитывая односвязный список, удалите n-й элемент из конца списка.
Вы должны сделать это за один проход и только с постоянной дополнительной памятью.
Приведенная выше иллюстрация предназначена для n==2, т. е. для входных данных {1,2,3,4,5} и n==2 результат равен {1,2,3,5}.
Прежде чем вы продолжите чтение, я рекомендую вам попробовать решить ее самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/bMdMnxbbn.
Решение
Сложность этой задачи в том, что она решается за один проход и с постоянной дополнительной памятью.
С O(n*n) мы могли бы многократно сканировать n элементов вперед. Однако, если подумать, это очень расточительно. Если мы знаем предыдущую пару элементов, которые находятся на расстоянии n друг от друга, мы можем перейти к следующей паре, просто переместив оба.
Это уже дает нам решение. Мы будем сканировать первую пару, а затем многократно продвигать пару итераторов, пока не найдем пару, в которой второй элемент находится в конце списка.
#include <forward_list>
void remove_nth_from_end(std::forward_list<int>& head, int n) {
// start with tail one ahead
auto node = head.before_begin();
auto tail = head.begin();
// advance it so it is n elements ahead
for (int i = 1; i < n && tail != head.end(); ++i)
++tail;
// if there aren't enough elements in the list
if (tail == head.end()) return;
// advance both iterators together
while (std::next(tail) != head.end()) {
++node;
++tail;
}
// remove the n-th element
head.erase_after(node);
}
