Chương trình xóa lần xuất hiện cuối cùng của giá trị mục tiêu trong danh sách liên kết trong Python

Mô tả bài toán

Cho danh sách liên kết đơn và giá trị target. Xóa lần xuất hiện cuối cùng của target trong danh sách.

Ví dụ: [5,4,2,6,5,2,3,2,4,5,4,7], target = 5 → đầu ra [5,4,2,6,5,2,3,2,4,4,7].

Giải thuật (Duyệt một lần, lưu nút trước lần cuối)

1. Khởi tạo head = node, k = None (nút target cuối cùng), prev = None (nút trước k), found = False.
2. Duyệt qua danh sách:
   • Nếu node.val == target: found = True, prev = k.
   • k = node, node = node.next.
3. Nếu không tìm thấy: trả về head.
4. Nếu prev là None (target ở đầu): trả về head.next.
5. Ngược lại: prev.next = prev.next.next, trả về head.

Ví dụ mã Python

class ListNode:
    def __init__(self, data, next=None):
        self.val = data
        self.next = next

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_list(head):
    ptr = head
    print('[', end="")
    while ptr:
        print(ptr.val, end=", ")
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, node, target):
        head = node
        k = None
        prev = None
        found = False
        while node:
            if node.val == target:
                found = True
                prev = k
            k = node
            node = node.next
        if found == False:
            return head
        if not prev:
            return head.next
        prev.next = prev.next.next
        return head

ob = Solution()
L = make_list([5,4,2,6,5,2,3,2,4,5,4,7])
target = 5
print_list(ob.solve(L, target))

Đầu vào

[5,4,2,6,5,2,3,2,4,5,4,7]

Đầu ra

[5, 4, 2, 6, 5, 2, 3, 2, 4, 4, 7, ]