Problem
Eine verkettete Liste speichert Werte in Knoten, die auf den nächsten Knoten zeigen, daher ist Einfügen und Entfernen am Anfang günstig. Simuliere eine Liste, die leer beginnt.
Verarbeite die Operationen der Reihe nach:
push_front x: x vorne einfügen.push_back x: x hinten einfügen.pop_front: den ersten Wert entfernen (bei leerer Liste ignoriert).remove x: den ersten Knoten mit dem Wert x entfernen, falls vorhanden.reverse: die Reihenfolge der Knoten umdrehen.
Implementiere linked_list_operations(operations).
Eingabe
operations: Die Operationen.
Ausgabe
Gib die Werte der Liste von vorne nach hinten zurück.
Einschränkungen
0 ≤ Anzahl der Operationen ≤ 10,000
−10^9 ≤ x ≤ 10^9
Beispiele
Eingabe:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
Erwartete Ausgabe:
expected = [3, 2, 1]Eingabe:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Erwartete Ausgabe:
std::vector<long long> expected = {3, 2, 1};Eingabe:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Erwartete Ausgabe:
long[] expected = new long[] {3, 2, 1};Erläuterung
Die Liste wächst zu 1 → 2 → 3, und umgedreht ergibt sie [3, 2, 1].
Eingabe:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
Erwartete Ausgabe:
expected = [5]Eingabe:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Erwartete Ausgabe:
std::vector<long long> expected = {5};Eingabe:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Erwartete Ausgabe:
long[] expected = new long[] {5};Erläuterung
remove entfernt nur die erste 5, übrig bleibt 7 → 5; pop_front entfernt dann 7: [5].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Ein Listentyp mit günstigem Einfügen vorne und hinten (std::list, LinkedList<T>, deque) erledigt das meiste.
Hinweis 2
remove löscht nur den ersten Treffer, und pop_front auf einer leeren Liste tut nichts.
Hinweis 3
Nach dem Umdrehen ist für spätere Pushes und Pops das andere Ende vorne.
Erwartete Komplexität
Zeit O(n²), zusätzlicher Speicher O(n)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.