Problème
Une liste chaînée stocke les valeurs dans des nœuds qui pointent vers le suivant, donc ajouter ou retirer en tête coûte peu. Simulez une liste qui commence vide.
Traitez les opérations dans l'ordre :
push_front x: ajoute x en tête.push_back x: ajoute x en queue.pop_front: retire la première valeur (ignoré si la liste est vide).remove x: retire le premier nœud de valeur x, s'il existe.reverse: inverse l'ordre des nœuds.
Implémentez linked_list_operations(operations).
Entrée
operations: Les opérations.
Sortie
Renvoyez les valeurs de la liste de la tête à la queue.
Contraintes
0 ≤ nombre d'opérations ≤ 10,000
−10^9 ≤ x ≤ 10^9
Exemples
Entrée :
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
Sortie attendue :
expected = [3, 2, 1]Entrée :
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Sortie attendue :
std::vector<long long> expected = {3, 2, 1};Entrée :
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Sortie attendue :
long[] expected = new long[] {3, 2, 1};Explication
La liste devient 1 → 2 → 3, et l'inverser donne [3, 2, 1].
Entrée :
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
Sortie attendue :
expected = [5]Entrée :
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Sortie attendue :
std::vector<long long> expected = {5};Entrée :
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Sortie attendue :
long[] expected = new long[] {5};Explication
remove ne retire que le premier 5, il reste 7 → 5 ; pop_front retire ensuite 7 : [5].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Un type de liste avec insertion rapide aux deux bouts (std::list, LinkedList<T>, deque) fait l'essentiel du travail.
Indice 2
remove ne supprime que la première correspondance, et pop_front sur une liste vide ne fait rien.
Indice 3
Après une inversion, l'autre bout devient la tête pour les push et pop suivants.
Complexité attendue
temps O(n²), espace supplémentaire O(n)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.