檢查連結串列中元素在 Python 中是否成對出現

假設我們有一個單向連結串列。我們必須檢查給定連結串列中的每個元素是否成對出現，換句話說，所有元素都出現偶數次。

因此，如果輸入像 list = [2,5,5,2,3,3]，則輸出將為 True。

要解決此問題，我們將遵循以下步驟 −

  • xor_res := 0，current_node := 連結串列頭
  • 當 current_node 不為 null 時，執行
    • xor_res := xor_res XOR current_node 的值
    • current_node := current_node 的下一個
  • 當 xor_res 為非零時返回 False，否則返回 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

更新於： 18-1-2021

245 次瀏覽

開啟你的 職業之旅

完成課程後獲得認證

開始學習
廣告