สมมติว่าเรามีรายการที่เชื่อมโยงกัน เราต้องตรวจสอบว่าแต่ละองค์ประกอบในรายการเชื่อมโยงที่กำหนดมีอยู่ในคู่หรือไม่หรืออีกนัยหนึ่งองค์ประกอบทั้งหมดเกิดขึ้นแม้กระทั่งไม่มี ครั้ง.
ดังนั้น หากอินพุตเป็นเหมือน list =[2,5,5,2,3,3] ผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- xor_res :=0, current_node :=ส่วนหัวของรายการที่เชื่อมโยง
- ในขณะที่ current_node ไม่เป็นโมฆะ ให้ทำ
- xor_res :=ค่า xor_res XOR ของ current_node
- current_node :=ถัดไปของ current_node
- คืนค่าเป็นเท็จเมื่อ xor_res ไม่ใช่ศูนย์ มิฉะนั้นจะเป็น True
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
[2,5,5,2,3,3]
ผลลัพธ์
True
