ปัญหา
กำหนด Singly Linked List ตรวจสอบว่าทุกค่าที่ปรากฏ มีจำนวนครั้งเป็นเลขคู่ (คืออยู่ในคู่)
ตัวอย่าง: [2,5,5,2,3,3] → ทุกตัวเป็นคู่ → True
แนวทางแก้ปัญหา
ใช้คุณสมบัติ XOR: x ^ x = 0 และ x ^ 0 = x หากทุกตัวเป็นคู่ XOR ทั้งหมดจะได้ 0
ตัวอย่างโค้ด
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 solve(head):
xor_res = 0
current_node = head
while current_node:
xor_res ^= current_node.val
current_node = current_node.next
return False if xor_res else True
head = make_list([2, 5, 5, 2, 3, 3])
print(solve(head)) # Trueอินพุต / เอาต์พุต
Input: [2,5,5,2,3,3] Output: True
