Giả sử chúng ta có một danh sách được liên kết đơn lẻ. Chúng ta phải kiểm tra xem mỗi phần tử trong danh sách liên kết đã cho có nằm trong một cặp hay không, hay nói cách khác là tất cả các phần tử đều xảy ra thậm chí không có. của thời gian.
Vì vậy, nếu đầu vào giống như list =[2,5,5,2,3,3], thì đầu ra sẽ là True.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- xor_res:=0, current_node:=đầu danh sách được liên kết
- trong khi current_node không null, hãy thực hiện
- xor_res:=xor_res Giá trị XOR của current_node
- current_node:=next of current_node
- trả về False khi xor_res khác 0, ngược lại là True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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 solve(head): xor_res = 0 current_node = head while current_node != None: xor_res = 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))
Đầu vào
[2,5,5,2,3,3]
Đầu ra
True