Chương trình xóa các mục trùng lặp trong danh sách liên kết bằng Python

Cho danh sách liên kết các số, xóa các số xuất hiện nhiều lần (chỉ giữ một lần xuất hiện đầu tiên), giữ nguyên thứ tự ban đầu.

Ví dụ: [2 → 4 → 6 → 1 → 4 → 6 → 9] → [2 → 4 → 6 → 1 → 9].

Quy trình giải quyết

1. Nếu danh sách không rỗng:
   • Tạo tập hợp seen.
   • Duyệt qua danh sách với con trỏ temp.
   • Thêm giá trị đầu tiên vào seen.
   • Trong khi temp.next tồn tại:
     • Nếu temp.next.val chưa có trong seen, thêm vào và tiến temp.
     • Ngược lại, bỏ qua nút trùng lặp: temp.next = temp.next.next.
2. Trả về đầu danh sách.

Ví dụ mã nguồn

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):
        if node:
            seen = set()
            temp = node
            seen.add(temp.val)
            while temp.next:
                if temp.next.val not in seen:
                    seen.add(temp.next.val)
                    temp = temp.next
                else:
                    temp.next = temp.next.next
            return node

ob = Solution()
head = make_list([2, 4, 6, 1, 4, 6, 9])
print_list(ob.solve(head))
# Output: [2, 4, 6, 1, 9, ]

Đầu vào

[2, 4, 6, 1, 4, 6, 9]

Đầu ra

[2, 4, 6, 1, 9, ]