Đề bài
Danh sách liên kết lưu giá trị trong các nút trỏ tới nút kế tiếp, nên thêm hoặc xóa ở đầu rất rẻ. Hãy mô phỏng một danh sách ban đầu rỗng.
Xử lý các thao tác theo thứ tự:
push_front x: thêm x vào đầu.push_back x: thêm x vào cuối.pop_front: xóa giá trị đầu tiên (bỏ qua nếu danh sách rỗng).remove x: xóa nút đầu tiên có giá trị x, nếu có.reverse: đảo ngược thứ tự các nút.
Hãy viết linked_list_operations(operations).
Đầu vào
operations: Các thao tác.
Đầu ra
Trả về các giá trị trong danh sách từ đầu đến cuối.
Ràng buộc
0 ≤ số thao tác ≤ 10,000
−10^9 ≤ x ≤ 10^9
Ví dụ
Đầu vào:
operations = ["push_back 2", "push_front 1", "push_back 3", "reverse"]
Kết quả mong đợi:
expected = [3, 2, 1]Đầu vào:
std::vector<std::string> operations = {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Kết quả mong đợi:
std::vector<long long> expected = {3, 2, 1};Đầu vào:
string[] operations = new string[] {"push_back 2", "push_front 1", "push_back 3", "reverse"};
Kết quả mong đợi:
long[] expected = new long[] {3, 2, 1};Giải thích
Danh sách thành 1 → 2 → 3, đảo ngược được [3, 2, 1].
Đầu vào:
operations = ["push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"]
Kết quả mong đợi:
expected = [5]Đầu vào:
std::vector<std::string> operations = {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Kết quả mong đợi:
std::vector<long long> expected = {5};Đầu vào:
string[] operations = new string[] {"push_back 5", "push_back 7", "push_back 5", "remove 5", "pop_front"};
Kết quả mong đợi:
long[] expected = new long[] {5};Giải thích
remove chỉ xóa số 5 đầu tiên, còn 7 → 5; pop_front xóa tiếp 7: [5].
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Một kiểu danh sách thêm nhanh ở cả hai đầu (std::list, LinkedList<T>, deque) làm phần lớn công việc.
Gợi ý 2
remove chỉ xóa phần tử khớp đầu tiên, và pop_front trên danh sách rỗng không làm gì.
Gợi ý 3
Đảo ngược làm đổi đầu nào là đầu danh sách cho các lệnh push và pop sau đó.
Độ phức tạp mong đợi
thời gian O(n²), bộ nhớ phụ O(n)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.