Viết hàm delete_last(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L

Trả lời câu hỏi SGK Tin 11 Kết nối tri thức trang 142: Viết hàm delete_last(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L (Bài 30: Thiết lập thư viện cho chương trình)

Câu hỏi: Viết hàm delete_last(L) có chức năng xoá phần tử cuối cùng của danh sách liên kết L

Trả lời ngắn gọn: 

Để xoá phần tử cuối cùng của danh sách liên kết, ta cần duyệt từ đầu danh sách đến nút cuối cùng sau đó xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó. Nếu danh sách rỗng hoặc chỉ có một phần tử thì ta chỉ cần xoá phần tử đó và trả về danh sách. Ta có thể sử dụng hàm delete_last() để xoá phần tử cuối cùng của danh sách liên kết.

Trả lời chi tiết:

Để xoá phần tử cuối cùng của danh sách liên kết ta cần duyệt từ đầu danh sách đến nút cuối cùng sau đó xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó. Nếu danh sách rỗng hoặc chỉ có một phần tử thì ta chỉ cần xoá phần tử đó và trả về danh sách. Mã nguồn Python cho hàm delete_last() như sau:

def delete_last(L):
   # Nếu danh sách rỗng, trả về None
   if L is None:
       return None
   
   # Nếu danh sách chỉ có một phần tử, xoá phần tử đó và trả về danh sách
   if L.next is None:
       del L
       return None
   
   # Tìm nút cuối cùng và nút trước nó
   prev_node = None
   curr_node = L
   while curr_node.next is not None:
       prev_node = curr_node
       curr_node = curr_node.next
   
   # Xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó
   prev_node.next = None
   del curr_node
   
   # Trả về danh sách đã được xoá phần tử cuối cùng
   return L

Giải thích:

- Nếu danh sách rỗng (tức là None), ta trả về None vì không có phần tử nào trong danh sách.

- Nếu danh sách chỉ có một phần tử (tức là chỉ có nút đầu tiên), ta xoá nút đó và trả về None vì danh sách sẽ trở thành rỗng.

- Nếu danh sách có hai phần tử trở lên, ta tìm nút cuối cùng và nút trước nó bằng cách duyệt từ đầu danh sách đến nút cuối cùng. Sau đó, ta xoá nút cuối cùng và cập nhật con trỏ next của nút trước nó để trỏ đến None.

- Cuối cùng, ta trả về danh sách đã được xoá phần tử cuối cùng.

Sau khi định nghĩa hàm này, ta có thể sử dụng nó để xoá phần tử cuối cùng của danh sách liên kết như sau:

# Định nghĩa một nút trong danh sách liên kết
class Node:
   def __init__(self, data=None):
       self.data = data
       self.next = None

# Tạo một danh sách liên kết đơn giản
danh_sach = Node(1)
danh_sach.next = Node(2)
danh_sach.next.next = Node(3)

# Xoá phần tử cuối cùng của danh sách liên kết
danh_sach = delete_last(danh_sach)

# In danh sách liên kết sau khi xoá phần tử cuối cùng
curr
>> Xem toàn bộ: Soạn Tin 11 Kết nối tri thức