Связный список хранит значения в узлах, которые указывают на следующий узел, поэтому добавлять и удалять в начале дёшево. Смоделируйте список, который сначала пуст.
Обработайте операции по порядку:
push_front x: добавить x в начало.push_back x: добавить x в конец.pop_front: удалить первое значение (игнорируется, если список пуст).remove x: удалить первый узел со значением x, если он есть.reverse: развернуть порядок узлов.
Реализуйте linked_list_operations(operations).
Входные данные
operations: Операции.
Выходные данные
Верните значения списка от начала к концу.
Ограничения
0 ≤ число операций ≤ 10,000
−10^9 ≤ x ≤ 10^9
Примеры
Ввод:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
Ожидаемый вывод:
expected = [3, 2, 1]Ввод:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Ожидаемый вывод:
std::vector<long long> expected = {3, 2, 1};Ввод:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Ожидаемый вывод:
long[] expected = new long[] {3, 2, 1};Пояснение
Список становится 1 → 2 → 3, а после разворота — [3, 2, 1].
Ввод:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
Ожидаемый вывод:
expected = [5]Ввод:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Ожидаемый вывод:
std::vector<long long> expected = {5};Ввод:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Ожидаемый вывод:
long[] expected = new long[] {5};Пояснение
remove удаляет только первую 5, остаётся 7 → 5; затем pop_front удаляет 7: [5].
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Тип списка с дешёвой вставкой в начало и конец (std::list, LinkedList<T>, deque) делает почти всю работу.
Подсказка 2
remove удаляет только первое совпадение, а pop_front на пустом списке ничего не делает.
Подсказка 3
После разворота началом для следующих push и pop становится другой конец.
Ожидаемая сложность
время O(n²), доп. память O(n)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.