Chương trình xóa tất cả nút có giá trị cho trước khỏi danh sách liên kết trong Python

Cho danh sách liên kết đơn và giá trị target, xóa tất cả nút có giá trị bằng target.

Ví dụ

Đầu vào: [5,8,2,6,5,2,9,6,2,4], target=2.
Đầu ra: [5, 8, 6, 5, 9, 6, 4].

Thuật toán

1. Lưu head = node.
2. Duyệt node:
   • Khi node.next.val == target, bỏ qua nút đó: node.next = node.next.next.
   • Tiến node = node.next.
3. Nếu head.val == target, trả về head.next, ngược lại trả về head.

Mã nguồn 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
        while node and node.next:
            while node.next.val == target:
                node.next = node.next.next
            node = node.next
        if head.val == target:
            return head.next
        else:
            return head

ob = Solution()
head = make_list([5,8,2,6,5,2,9,6,2,4])
ob.solve(head, 2)
print_list(head)

Đầu vào / Đầu ra

Input: [5,8,2,6,5,2,9,6,2,4]
Output: [5, 8, 6, 5, 9, 6, 4, ]