Problema
Una lista concatenata salva i valori in nodi che puntano al successivo, quindi aggiungere o togliere in testa costa poco. Simulane una che parte vuota.
Elabora le operazioni in ordine:
push_front x: aggiunge x in testa.push_back x: aggiunge x in coda.pop_front: rimuove il primo valore (ignorato se la lista è vuota).remove x: rimuove il primo nodo con valore x, se esiste.reverse: inverte l'ordine dei nodi.
Implementa linked_list_operations(operations).
Input
operations: Le operazioni.
Output
Restituisci i valori della lista dalla testa alla coda.
Vincoli
0 ≤ numero di operazioni ≤ 10,000
−10^9 ≤ x ≤ 10^9
Esempi
Input:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
Output atteso:
expected = [3, 2, 1]Input:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Output atteso:
std::vector<long long> expected = {3, 2, 1};Input:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Output atteso:
long[] expected = new long[] {3, 2, 1};Spiegazione
La lista diventa 1 → 2 → 3 e invertendola si ottiene [3, 2, 1].
Input:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
Output atteso:
expected = [5]Input:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Output atteso:
std::vector<long long> expected = {5};Input:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Output atteso:
long[] expected = new long[] {5};Spiegazione
remove toglie solo il primo 5 e resta 7 → 5; poi pop_front toglie 7: [5].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Un tipo di lista con inserimenti economici in testa e in coda (std::list, LinkedList<T>, deque) fa quasi tutto il lavoro.
Suggerimento 2
remove elimina solo la prima corrispondenza, e pop_front su una lista vuota non fa nulla.
Suggerimento 3
Dopo l'inversione, l'altra estremità diventa la testa per i push e pop successivi.
Complessità attesa
tempo O(n²), spazio aggiuntivo O(n)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.