Tìm bằng cách đi theo next
Từ `head`, cứ theo `next` cho đến khi gặp khóa k hoặc `None`. Nếu có hai nút cùng khóa, cách duyệt này trả **nút gặp đầu tiên**. Khi xóa, cần phân biệt nút đầu với nút sau: xóa đầu bằng `L.head = L.head.next`. Với nút ở giữa, giữ nút đứng trước `truoc` và nút cần xóa `x`, rồi gán `truoc.next = x.next` để nối qua x. Nếu không thấy khóa thì giữ danh sách nguyên. Chỉ cần `None` để biểu thị không thấy; không nhầm với khóa có giá trị 0.
Hai hàm dùng lại Node và LL
```python
def tim(L, k):
x = L.head
while x is not None and x.key != k:
x = x.next
return x
def xoa_khoa(L, k):
truoc, x = None, L.head
while x is not None and x.key != k:
truoc, x = x, x.next
if x is None:
return False
if truoc is None:
L.head = x.next
else:
truoc.next = x.next
return True
L = LL()
for k in [8, 2, 5]:
chen_dau(L, k)
print(cac_khoa(L), tim(L, 2).key)
print(xoa_khoa(L, 2), cac_khoa(L))
```
Đoạn này dùng `Node`, `LL`, `chen_dau` và `cac_khoa` của bài trước; đặt chung tệp hoặc nhập các hàm đã lưu. Kết quả là `[5, 2, 8] 2` rồi `True [5, 8]`. `xoa_khoa` trả `False` khi không tìm thấy và không đổi danh sách. Với hai khóa giống nhau, chỉ lần xuất hiện đầu tiên bị xóa; muốn xóa tất cả phải lặp hoặc viết thuật toán khác.
Bài luyện
Với `head → 5 → 2 → 8 → None`, sau khi xóa khóa 2 thì chuỗi nào đúng?
Nút 5 trỏ qua nút 2 đến nút 8.
Nút 2 là nút cần xóa.
Nút 8 vẫn thuộc danh sách.
Xóa không đổi thứ tự các nút còn lại.
Lời giải
Giữ nút trước là 5 và gán next của 5 bằng next của 2, tức nút 8; chuỗi thành 5→8.
Bài luyện
Nếu xóa nút đầu tiên, cần cập nhật tham chiếu nào?
head phải chỉ tới nút kế tiếp của đầu cũ.
Như vậy chưa xóa gì.
key không dùng để nối.
Không cần đổi dữ liệu các nút.
Lời giải
Với nút đầu là x, phép L.head = x.next bỏ x khỏi chuỗi bắt đầu từ head.
Bài luyện
Nếu không có khóa cần xóa, `xoa_khoa` làm gì?
Vòng duyệt tới None và không thay liên kết.
Không chọn nút bất kì.
Hàm không chèn.
Không tìm thấy nên không thể báo đã xóa.
Lời giải
Khi x là None, hàm trả False trước mọi lệnh đổi head hoặc next.
Đang học