Pythonで連結リストの要素がすべてペアで存在するかどうかを確認する方法

問題の概要

片方向連結リストが与えられたとき、リスト内のすべての要素がペア(2個ずつ)で存在するかどうか、言い換えれば、すべての要素が偶数回出現しているかどうかを判定します。

例えば、入力が [2,5,5,2,3,3] の場合、各要素は2回ずつ出現しているため、出力は True になります。

解決アプローチ:XOR(排他的論理和)の活用

この問題は、XOR演算の性質を利用すると効率的に解くことができます。XORには次のような重要な性質があります。

• 同じ値同士のXORは0になる(x XOR x = 0)
• 任意の値と0のXORは元の値になる(x XOR 0 = x)
• XORは交換法則・結合法則が成り立つ

したがって、連結リストの全要素を先頭から順にXORしていき、すべての要素が偶数回出現していれば、最終的な結果は必ず0になります。逆に、1つでも奇数回出現する要素が存在すれば、結果は0以外になります。

アルゴリズムの手順

1. xor_res を 0 に初期化し、current_node を連結リストの先頭(head)に設定します。
2. current_node が None でない間、以下を繰り返します。
   • xor_res に current_node の値をXORします。
   • current_node を次のノードに進めます。
3. ループ終了後、xor_res が 0 以外なら False を、0 なら True を返します。

このアルゴリズムの時間計算量は O(n)、追加のメモリ使用量は O(1) であり、非常に効率的です。

実装例(Python)

以下の実装を見ると、より理解が深まります。

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

まとめ

XOR演算を利用することで、ハッシュマップなどの追加データ構造を使わずに、O(1)の追加メモリだけで連結リストの要素がすべてペアで存在するかどうかを判定できます。なお、この手法はリストの値が整数である場合に有効である点に注意してください。