Danh sách liên kết đơn: thêm cuối, đảo chiều, đếm phần tử
Danh sách liên kết đơn không lưu các phần tử cạnh nhau trong bộ nhớ, mà nối chúng bằng con
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: python-basics, python-classes-intro, python-while-loop.
Nội dung đề bài
Mô tả bài toán
Danh sách liên kết đơn không lưu các phần tử cạnh nhau trong bộ nhớ, mà nối chúng bằng con trỏ: mỗi nút biết nút kế tiếp của mình. Vì thế không thể truy cập phần tử thứ i trực tiếp, nhưng đổi chỗ các liên kết lại rất rẻ. Đảo chiều danh sách là bài tập kinh điển để hiểu cách con trỏ chạy.
Yêu cầu
Cài đặt lớp LinkedList biểu diễn một danh sách liên kết đơn rỗng lúc khởi tạo, với:
- init(self): tạo danh sách rỗng, không cần tham số.
- append(self, value): thêm một nút mang value vào cuối danh sách; trả về None.
- to_list(self): trả về danh sách Python chứa các giá trị theo thứ tự từ đầu tới cuối.
- reverse(self): đảo chiều danh sách tại chỗ bằng cách đổi các liên kết; trả về None.
- length(self): trả về số nút đang có.
Quy ước nộp bài
Nộp lớp LinkedList trong solution.py. Hệ thống khởi tạo lớp rồi gọi phương thức trực tiếp và so danh sách kết quả; không dùng stdin và không in ra stdout.
Input
Hệ thống khởi tạo lớp không kèm tham số, sau đó gọi lần lượt các phương thức theo kịch bản của từng bộ test. Giá trị thêm vào là số nguyên hoặc chuỗi.
Output
Giá trị trả về của từng lời gọi, theo đúng thứ tự đã gọi: append và reverse trả về None, to_list trả về danh sách, length trả về số nguyên.
Ràng buộc
- Số nút từ 0 đến 20; danh sách rỗng phải được xử lý trơn tru ở mọi phương thức.
- reverse phải đổi liên kết thật sự, không tạo danh sách mới rồi trả về.
- to_list trả về danh sách mới, không phải tham chiếu tới cấu trúc bên trong.
- Không dùng list của Python để lưu các phần tử thay cho các nút liên kết.
Ví dụ 1
Input
LinkedList(init={}, methods=[{"method": "append", "args": [1]}, {"method": "append", "args": [2]}, {"method": "append", "args": [3]}, {"method": "to_list"}, {"method": "length"}])
Output
[null, null, null, [1, 2, 3], 3]
Ví dụ 2
Input
LinkedList(init={}, methods=[{"method": "append", "args": [5]}, {"method": "reverse"}, {"method": "to_list"}])
Output
[null, null, [5]]
Giải thích
Gọi append(1), append(2), append(3) thì to_list() cho [1, 2, 3] và length() cho 3. Nếu sau đó gọi reverse() thì to_list() cho [3, 2, 1].
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
