Kiểm tra phần tử linked list xuất hiện theo cặp (xử lý XOR) trong Python

Cho singly linked list. Kiểm tra mọi giá trị đều xuất hiện chẵn lần (tức là có thể ghép thành cặp). Dùng tính chất XOR: x ^ x = 0, x ^ 0 = x.

Ví dụ: [2,5,5,2,3,3] → XOR tất cả = 0 → True.

Triển khai

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

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

def solve(head):
    xor_res = 0
    cur = head
    while cur:
        xor_res ^= cur.val
        cur = cur.next
    return xor_res == 0

head = make_list([2, 5, 5, 2, 3, 3])
print(solve(head))  # True

Đầu vào / Đầu ra

Input: [2,5,5,2,3,3]
Output: True

Lưu ý: Phương pháp này chỉ đúng khi mọi phần tử xuất hiện chẵn lần. Nếu có phần tử xuất hiện 4 lần vẫn trả về True.